B3732 [信息与未来 2017] 任务调度
chen_zhe
·
·
题解
欢迎报名洛谷网校，期待和大家一起进步！
本题考察贪心。
根据题意，惩罚值等于所有任务完成时刻之和。例如，有 2 个任务分别需要 10 和 20 单位时间完成。如果先完成任务 1，惩罚值为 10+30=40；如果先完成任务 2，惩罚值为 20+30=50。这提示我们，若有多个任务需要完成，将任务按处理时间从小到大排序完成，可能是最优的方案。
假设 a_i 已经从小到大排序，考虑每个任务的完成时间：
- 第一个任务：C_1=a_1；
- 第二个任务：C_2=a_1+a_2；
- 第三个任务：C_3=a_1+a_2+a_3；
- 以此类推；
- 第 n 个任务：C_n=a_1+a_2+a_3+\dots+a_n；
- 答案为：S=C_1+C_2+C_3+\dots+C_n。
将所有的 C_1,C_2,C_3,\dots C_n 展开可得出，a_i 会在答案中出现 n-i+1 次。因此，计算方式应当如下列代码所示：
sort(a + 1, a + 1 + n);
for (int i = 1; i <= n; i++) {
ans += 1LL * a[i] * (n - i + 1);
}
如果只是完成该题，那么上面的分析已经足够了。下面，我们来证明为什么若有多个任务需要完成，将任务按处理时间从小到大排序完成，是最优的方案。这一证明需要使用排序不等式（Rearrangement Inequality）。
排序不等式指出，若 a_1\leq a_2\leq a_3\leq \dots \leq a_n，b_1\leq b_2\leq b_3\leq \dots \leq b_n，而 c_1,c_2,c_3,\dots,c_n 为 b_1,b_2,b_3,\dots,b_n 的乱序排列，则有：
\sum_{i=1}^n a_ib_{n-i+1} \leq \sum_{i=1}^n a_ic_i \leq \sum_{i=1}^n a_ib_i
也就是说：
- 当一个序列递增，另一个递减时，元素按顺序配对的乘积和最大；
- 反之，将最小值与最大系数配对（即升序排列），得到最小和。
带入这一题来说：
S=n\times a_1+(n-1)\times a_2+(n-2)\times a_3+\dots+1\times a_n
其中，系数 n,n-1,n-2,\dots,1 是递减的，而 a_1,a_2,a_3,\dots a_n 是递增的，恰好是排序不等式中最左边的一项，也就是所有情况中的最小值。从而贪心思路是正确的。排序不等式是此类排序贪心题的正确性说理证明的一大工具，需要多加学习应用。