自动搬运

查看原文

来自洛谷，原作者为

	chen_zhe Aya 敲可爱的~

搬运于2025-08-24 21:14:41，当前版本为作者最后更新于2025-03-07 17:09:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

欢迎报名洛谷网校，期待和大家一起进步！

本题考察贪心。

根据题意，惩罚值等于所有任务完成时刻之和。例如，有 $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$ 是递增的，恰好是排序不等式中最左边的一项，也就是所有情况中的最小值。从而贪心思路是正确的。排序不等式是此类排序贪心题的正确性说理证明的一大工具，需要多加学习应用。