一个典题的结论

结论

有 $N$ 个任务，第 $i$ 个任务需要被执行 $A_i$ 次，每次可以选至多 $k$ 个互不相同的任务各执行一次，则完成所有任务的最少次数为

证明

下界

每次最多执行 $k$ 个任务，故 $T\ge\left\lceil \dfrac{\sum A_i}{k} \right\rceil$ ；同一个任务每次只能执行一次，故 $T\ge\max A_i$ ．

可行性

构造 $k$ 条长度为 $T$ 的数轴（第 $1$ 条轴到第 $k$ 条轴首尾相接，总长 $kT$）．

轴1: ─────────────────
轴2: ─────────────────
...
轴k: ─────────────────

把各任务以执行次数 $A_i$ 为长度依次从上往下、从左往右铺满（总长度 $S \le kT$ ）．若某个任务跨越两条轴的交界，则从交界点截断，分成两段分别放在相邻两条轴的尾部和头部．

第 $i$ 次执行每条轴上点 $i-1$ 到点 $i$ 对应的任务，共执行 $T$ 次．

因为 $A_i \le T$，所以任意被截成的两段的任务一定分布在相邻两条轴的不同位置（即尾部一定在头部的右边），不会在同一列（同一次）出现．

故每次执行的任务一定 $\le k$ 个且互不相同，满足约束．