STEP5 Problem 0028 : 禮品分配

題目：

給 N 個物品，每個物品有製作時間 ti 及交貨期限 di ，若完成時間 ei 超出交貨期限

則必須罰 ei - di 分，現在你只在意所有 penalty 中最大和次大的物品，請問你要怎麼

分配物品的製作順序，使得前兩大 penalty 和最小呢？

(N <= 5000)


解法：

先簡化題目的條件，若改成只在意 penalty 最大的物品，事實上可以再轉換成，

將所有物品的 di 都同加上某個 xi ，使得所有物品都可以在時限內完成，此時 xi

的最小值即為 penalty 最大的物品，轉換後的題目怎麼解決呢？首先將所有物品依照

di 作排序，可以簡單證明，若 A 物品的 da < B 物品的 db ，此時 A 先做一定不會

比較差，故按照此次序做下去即為最佳解，也可以發現 xi 根本不需要枚舉或二分搜

等等就可以求出來，回到原題目，我們已經求出簡化題的 O(NlgN) 解法，同樣地，

我們先對所有 di 作排序，然後枚舉 penalty 為最大的物品，再枚舉欲插入的位置，

同時找出此時 penalty 為第二大的物品，若成立就更新當前最佳解。由於物品順序

會有更動，故求出當前第二大 penalty的物品時，需要用到區間最大值並加減調動後

的時間，我們可以透過預處理得到 O(NlgN, 1)的 RMQ 算法，至此，題目已獲得

O(N^2lgN) 的解法。