alan23273850 的刷題筆記
a567: 死線排程
Tags: greedy, scheduling
出處：https://zerojudge.tw/ShowProblem?problemid=a567
提交：https://zerojudge.tw/Submissions?problemid=a567&account=allllllan123456
問題：給定 $N\in[1,10000]$ 項工作，每項工作有各自的整數死線日期 $d_i\in[1,10000]$ 和利益 $p_i\in[1,32766]$，每項工作都可以在第 1 到 $d_i$ 天的其中一天內完成，但每天最多只能進行一項工作。請問如何排程能得到總利益的最大值？求此最大值。
解法：這題也是很經典的 greedy 演算法，先把所有工作按照利益由大到小排序，接著按照此順序依序安排執行日期，每項工作安排的方式是由自己的死線開始看，如果有空位就放，沒空位就往前一格繼續看，直到有空位放為止，如果都沒有空位放就只能放棄這項工作，那麼每項工作都考慮過之後就算是安排完畢。
證明：既然是 greedy 演算法，就要用標準方式證明。現在我們想說明每次對於尚未決定好安置日期之最大利益工作 $w_i$ 的安排方式，上述方法絕不會錯，只要說明其他方法都不優於上述方法，上述方法就是最佳選擇。先列出對於 $w_i$ 的三種可能選擇，選項 (1) 安排在死線 $d_i$ 之前 (含死線當天) 但最靠近死線的空位 (姑且稱為 X)，選項 (2) 安排在死線 $d_i$ 之前但放在 Y，注意到 Y $\ne$ X，選項 (3) 直接放棄此工作。先討論選項 (2)，假設此選項現在這個時候也能獲得局部最佳解，那麼我必定可以把目前放在 Y 的 $w_i$ 改移至 X，如果在改移之前 X 上面剛好又有其他工作 $w_j$ 的話，它必定也可以改放在 Y 上面，如此一來就能說明選項 (2) 的總利益也能由選項 (1) 達成。再來討論選項 (3)，選項 (3) 和選項 (1) 的差別在於少了一個 $w_i$ 的可能性，對於任何一個選項 (3) 的安置方式，我勢必可以把它最前面的空位 (無論是否已有工作占據) 取代為 $w_i$，如此一來便說明了選項 (3) 的局部最佳解不可能優於選項 (1) 或選項 (2)。綜合上述，我們便可以推得選項 (1) 必定為最佳選項，一路按照此要領操作下去便能得到最優安排。
1#include <bits/stdc++.h>
2using namespace std;
3
4int n, deadline[10000], ids[10000], profit[10000], task[10001];
5
6int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
7 while (cin >> n) {
8 int maxDL = -1;
9 for (int i=0; i<n; i++) {
10 cin >> deadline[i] >> profit[i];
11 if (deadline[i] > maxDL) maxDL = deadline[i]; // 更新最久遠的 deadline
12 ids[i] = i;
13 }
14 memset(task+1, 0, maxDL*sizeof(int)); // 初始化每個日期被完成的 task 的利益
15 sort(ids, ids+n, [](int a, int b) { return profit[a] > profit[b]; });
16 for (int i=0; i<n; i++) {
17 int id = ids[i];
18 int day = deadline[id];
19 while (day && task[day]) day--;
20 if (day) task[day] = profit[id];
21 }
22 cout << accumulate(task+1, task+maxDL+1, 0) << '\n';
23 }
24 return 0;
25}