前陣子在題庫里刷到一道題題名叫《學(xué)習(xí)軌跡》標(biāo)簽只有一個(gè)“貪心”。說實(shí)話第一眼看過去我還以為是什么樹上拓?fù)?、依賴?guī)劃之類的硬核題結(jié)果把題面讀完之后發(fā)現(xiàn)模型特別干凈有若干個(gè)學(xué)習(xí)任務(wù)每個(gè)任務(wù)有自己的耗時(shí)和截止時(shí)間你要決定做哪些任務(wù)、按什么順序做最后在“所有任務(wù)都不晚于截止時(shí)間”的前提下讓完成的任務(wù)數(shù)量盡可能多并輸出一條合法的完成順序。這其實(shí)就是一道特別典型的“反悔貪心”題只是包裝了一層“學(xué)習(xí)軌跡”的外殼。這篇博客就把我從讀題到推導(dǎo)、證明、寫代碼、對(duì)拍調(diào)試的完整過程都記錄下來希望對(duì)準(zhǔn)備算法競賽或者面試的朋友有幫助。1. 問題模型與核心切入思路1.1 把“學(xué)習(xí)軌跡”翻譯成數(shù)學(xué)語言先不急著上手寫代碼而是把題目抽象一下?，F(xiàn)在有 n 個(gè)學(xué)習(xí)任務(wù)每個(gè)任務(wù)有兩個(gè)關(guān)鍵屬性耗時(shí) ( t_i )做這個(gè)任務(wù)需要連續(xù)占用多少時(shí)間截止時(shí)間 ( d_i )這個(gè)任務(wù)必須在時(shí)刻 ( d_i ) 之前含完成。另外還有一個(gè)隱含限制同一時(shí)刻只能做一個(gè)任務(wù)任務(wù)一旦開始就不能中途停止必須一次性做完。你可以選擇任意多個(gè)任務(wù)來做也可以跳過某些任務(wù)。目標(biāo)很簡單在保證每個(gè)被選任務(wù)都能按時(shí)完成的前提下讓完成的任務(wù)數(shù)量最多。這里“學(xué)習(xí)軌跡”其實(shí)就是最終的任務(wù)完成順序。比如你決定做任務(wù) A、D、C那完成順序可能是 A → D → C這個(gè)順序就是一條軌跡。題目要求輸出這條軌跡本質(zhì)上就是要求你給出一個(gè)合法的、最優(yōu)的調(diào)度方案。1.2 為什么固定一個(gè)任務(wù)集合時(shí)按截止時(shí)間排序是最優(yōu)的假設(shè)你已經(jīng)決定要做某個(gè)任務(wù)集合 S那么 S 里這些任務(wù)按什么順序做最好答案是按截止時(shí)間從小到大排序。這個(gè)結(jié)論很關(guān)鍵是整個(gè)貪心策略的地基。我們用一個(gè)簡單的交換論證來解釋。假設(shè)當(dāng)前有一個(gè)執(zhí)行順序其中相鄰兩個(gè)任務(wù) i 和 j 是逆序的也就是說 ( d_i d_j )但任務(wù) i 排在任務(wù) j 前面。這時(shí)候把它們的順序交換一下不會(huì)讓任何任務(wù)變晚反而會(huì)更好。設(shè)這兩個(gè)任務(wù)開始前的累計(jì)耗時(shí)為 T。原來的順序是先 i 后 j那么i 的完成時(shí)刻是 ( T t_i )j 的完成時(shí)刻是 ( T t_i t_j )。因?yàn)?j 的截止時(shí)間更早所以風(fēng)險(xiǎn)在于 ( T t_i t_j ) 很可能超過 ( d_j )。交換之后變成先 j 后 ij 的完成時(shí)刻是 ( T t_j )它比原來的 ( T t_i t_j ) 小所以更安全i 的完成時(shí)刻是 ( T t_j t_i )它和原來 j 的完成時(shí)刻一樣但 i 的截止時(shí)間比 j 晚所以也更容易滿足。所以任意一個(gè)存在逆序?qū)Φ捻樞蚨伎梢酝ㄟ^若干次交換變成按截止時(shí)間升序的順序而且不會(huì)破壞任何任務(wù)的截止約束。換句話說對(duì)于一個(gè)固定的任務(wù)集合按截止時(shí)間升序執(zhí)行就是最優(yōu)的執(zhí)行順序。這一步想明白之后問題就從“排列 選擇”簡化成了“只選擇任務(wù)選完之后統(tǒng)一按截止時(shí)間排序執(zhí)行”。1.3 從“選集合”到“逐個(gè)加入 反悔”如果只是固定集合問題已經(jīng)很簡單了但集合本身需要選擇。直接枚舉子集是 ( O(2^n) )完全不可行。我們需要一個(gè)能夠在掃描過程中不斷做決定的方案。一個(gè)很自然的想法是把所有任務(wù)按截止時(shí)間從小到大排序然后從早到晚依次“嘗試”加入當(dāng)前計(jì)劃。每加入一個(gè)新任務(wù)如果發(fā)現(xiàn)當(dāng)前計(jì)劃超時(shí)了就從已經(jīng)選中的任務(wù)里刪掉一個(gè)讓計(jì)劃重新變合法。這種“先加入、超時(shí)了再刪掉一個(gè)”的做法就是反悔貪心。它和普通貪心的區(qū)別在于普通貪心一旦決定就不改了而反悔貪心允許你臨時(shí)反悔把之前某個(gè)決定撤銷掉。關(guān)鍵是刪掉哪一個(gè)這就是《學(xué)習(xí)軌跡》這道題真正的考點(diǎn)。2. 貪心策略推導(dǎo)與正確性證明2.1 掃描過程的核心維護(hù)量假設(shè)我們已經(jīng)把任務(wù)按截止時(shí)間升序排好了。掃描到第 i 個(gè)任務(wù)時(shí)維護(hù)兩個(gè)東西now當(dāng)前已經(jīng)選中的所有任務(wù)按截止時(shí)間升序執(zhí)行最后一個(gè)任務(wù)完成所需的累計(jì)耗時(shí)一個(gè)數(shù)據(jù)結(jié)構(gòu)用來記錄當(dāng)前已選任務(wù)中“耗時(shí)最大”的任務(wù)。每遇到一個(gè)新任務(wù) i先不管三七二十一把它加進(jìn)計(jì)劃里然后讓now t_i。這時(shí)候如果now d_i說明新任務(wù)排在當(dāng)前所有已選任務(wù)的最末尾也能在自己的截止時(shí)間前完成所以當(dāng)前計(jì)劃合法繼續(xù)往下掃描。如果now d_i說明把任務(wù) i 加進(jìn)來之后至少有一個(gè)任務(wù)的完成時(shí)間來不及了。這時(shí)候必須從當(dāng)前已選任務(wù)中刪掉一個(gè)。因?yàn)槿蝿?wù)數(shù)量目標(biāo)是要最大化刪掉一個(gè)之后數(shù)量會(huì)回到原來的大小但我們剛剛嘗試過“加入一個(gè)”所以總體數(shù)量比原來多 0。我們要做的選擇就是刪掉哪一個(gè)讓剩下的集合對(duì)后續(xù)掃描最有利。2.2 超時(shí)之后為什么刪“耗時(shí)最大”的任務(wù)這是整個(gè)貪心算法最核心的判斷。不妨想一想刪掉一個(gè)任務(wù)之后會(huì)發(fā)生什么第一已選任務(wù)的數(shù)量減少 1 第二當(dāng)前累計(jì)耗時(shí)now會(huì)減少被刪任務(wù)的耗時(shí)t。對(duì)于后面的任務(wù)來說它們關(guān)心什么只關(guān)心兩件事已經(jīng)完成了多少個(gè)任務(wù)以及當(dāng)前累計(jì)耗時(shí)還有多少。累計(jì)耗時(shí)越小后面插入新任務(wù)的空間就越大。因此當(dāng)必須刪一個(gè)任務(wù)時(shí)刪除耗時(shí)最大的那個(gè)任務(wù)可以讓now下降得最多留給后面的余量最大。但這樣會(huì)不會(huì)損失什么比如被刪掉的那個(gè)任務(wù)截止時(shí)間特別早后面有一個(gè)截止時(shí)間更晚的任務(wù)被保留了這會(huì)不會(huì)導(dǎo)致問題不會(huì)。因?yàn)榻刂箷r(shí)間更早的任務(wù)本身在加入時(shí)已經(jīng)驗(yàn)證過合法了即使刪掉它也不會(huì)讓其他更早的任務(wù)變差而保留了截止時(shí)間更晚的任務(wù)只會(huì)在執(zhí)行順序上排在更后面對(duì)前面任務(wù)的完成時(shí)間沒有任何影響。反過來如果刪掉一個(gè)耗時(shí)較小但截止時(shí)間較晚的任務(wù)保留耗時(shí)最大的任務(wù)那么now下降得少而且耗時(shí)最大的任務(wù)還很占地方顯然更不利于后續(xù)。我們還可以從“支配”的角度來理解。當(dāng)被迫要?jiǎng)h一個(gè)任務(wù)時(shí)我們面臨兩個(gè)候選方案方案 A 刪除耗時(shí)最大的任務(wù)方案 B 刪除另一個(gè)任務(wù)。方案 A 和方案 B 的任務(wù)數(shù)量相同但方案 A 的累計(jì)耗時(shí)更小。由于任務(wù)都可以按截止時(shí)間升序執(zhí)行累計(jì)耗時(shí)更小的方案里每個(gè)任務(wù)的完成時(shí)刻都不會(huì)比另一個(gè)方案更晚。也就是說方案 A 在可行性上支配了方案 B。所以刪除耗時(shí)最大的任務(wù)一定不會(huì)比刪除其他任務(wù)差。2.3 用“不變量”來總結(jié)正確性上面是直觀理解如果想讓自己更安心可以引入一個(gè)不變量來總結(jié)。假設(shè)掃描完前 i 個(gè)任務(wù)之后算法維護(hù)的集合 S 滿足在所有“僅從前 i 個(gè)任務(wù)中選出、并且能全部按時(shí)完成”的集合中S 的任務(wù)數(shù)最多在任務(wù)數(shù)最多的所有可行集合中S 的累計(jì)耗時(shí)最小。初始時(shí) S 為空顯然滿足。加入新任務(wù) i 后如果直接合法那么任務(wù)數(shù)增加 1達(dá)到理論上界且總耗時(shí)是在原最優(yōu)集合基礎(chǔ)上加上 t_i可以論證它仍然是最小總耗時(shí)的集合。如果超時(shí)了說明想在前 i 個(gè)任務(wù)中實(shí)現(xiàn)比當(dāng)前任務(wù)數(shù)多 1 的可行集合是不可能成功的于是我們回到原來的任務(wù)數(shù)此時(shí)為了保持“任務(wù)數(shù)最多且總耗時(shí)最小”必須從當(dāng)前集合中去掉一個(gè)任務(wù)。去掉耗時(shí)最大的任務(wù)得到的集合在同樣任務(wù)數(shù)中總耗時(shí)最小不變量繼續(xù)成立。這個(gè)不變量成立意味著算法最終得到的一定是全局最優(yōu)任務(wù)數(shù)量最多而且在相同數(shù)量下累計(jì)耗時(shí)最小。這也是為什么它比 DP 更高效但不會(huì)比 DP 更差。2.4 幾個(gè)容易被忽略的細(xì)節(jié)細(xì)節(jié)一只檢查當(dāng)前任務(wù)的截止時(shí)間夠不夠有人會(huì)擔(dān)心插入新任務(wù)后之前那些截止時(shí)間更早的任務(wù)會(huì)不會(huì)被影響不會(huì)。因?yàn)槲覀兪冀K是按截止時(shí)間升序掃描的新插入的任務(wù)在最終執(zhí)行順序里一定排在所有已有任務(wù)之后。它不會(huì)改變前面任何一個(gè)任務(wù)的開始時(shí)間所以前面任務(wù)的完成時(shí)刻不會(huì)因?yàn)樾氯蝿?wù)的插入而變大。只要新任務(wù)自身在它的截止時(shí)間前完成整個(gè)集合就合法。細(xì)節(jié)二刪掉的可能就是剛加入的任務(wù)如果新任務(wù)的耗時(shí)特別大比如 ( t_i d_i )那么它一加入就會(huì)超時(shí)刪除耗時(shí)最大的任務(wù)時(shí)刪除的可能就是它自己。這相當(dāng)于“嘗試加入后立刻放棄”是完全正常的。這個(gè)操作保證了算法不會(huì)強(qiáng)行選擇一個(gè)本身就不可能按時(shí)完成的任務(wù)。細(xì)節(jié)三全部任務(wù)都無法完成怎么辦極端情況下可能每個(gè)任務(wù)單獨(dú)做都會(huì)超時(shí)例如所有任務(wù)的 ( t_i d_i )。那么算法會(huì)不斷地加入、刪自己最后堆為空答案為 0。這種情況也要在實(shí)現(xiàn)上兼容輸出空軌跡即可。3. 代碼實(shí)現(xiàn)與手工模擬3.1 為什么選大根堆我們需要反復(fù)拿到當(dāng)前已選任務(wù)中耗時(shí)最大的那個(gè)并且還可能隨時(shí)加入新任務(wù)。這個(gè)需求恰好是“優(yōu)先隊(duì)列”最擅長的。C 里可以用priority_queue默認(rèn)就是大根堆堆頂是最大值。Python 里heapq是小根堆所以存耗時(shí)的時(shí)候取負(fù)數(shù)模擬大根堆。實(shí)現(xiàn)時(shí)還要注意一點(diǎn)題目最后要求輸出軌跡而堆里只能快速拿到最大元素沒有辦法按截止時(shí)間升序輸出所有元素。所以我們需要額外維護(hù)一個(gè)標(biāo)記數(shù)組記錄哪些任務(wù)在最終集合中。最后再按照一開始排好的截止時(shí)間順序掃描一遍把標(biāo)記為存活的任務(wù)輸出這個(gè)順序就是合法軌跡。3.2 C 參考實(shí)現(xiàn)#include bits/stdc.h using namespace std; struct Task { long long t; // 耗時(shí) long long d; // 截止時(shí)間 int id; // 原始編號(hào) }; int main() { int n; cin n; vectorTask tasks(n); for (int i 0; i n; i) { cin tasks[i].t tasks[i].d; tasks[i].id i 1; } // 核心第一步按截止時(shí)間升序排序 sort(tasks.begin(), tasks.end(), [](const Task a, const Task b) { return a.d b.d; }); // 大根堆pair耗時(shí), 編號(hào) priority_queuepairlong long, int pq; vectorchar alive(n 1, 0); long long now 0; for (auto task : tasks) { pq.push({task.t, task.id}); alive[task.id] 1; now task.t; if (now task.d) { auto [mx, id] pq.top(); pq.pop(); alive[id] 0; now - mx; } } vectorint ans; for (auto task : tasks) { if (alive[task.id]) { ans.push_back(task.id); } } cout ans.size() \n; for (int i 0; i (int)ans.size(); i) { cout ans[i] (i 1 (int)ans.size() ? \n : ); } return 0; }這段代碼可以直接 AC 常規(guī)版本。需要注意now和task.d都用long long因?yàn)楹臅r(shí)和截止時(shí)間都可能很大累加之后很容易超出int的范圍。3.3 Python 參考實(shí)現(xiàn)import heapq def main(): n int(input()) tasks [] for i in range(n): t, d map(int, input().split()) tasks.append((d, t, i 1)) tasks.sort() # 按截止時(shí)間 d 升序 heap [] # 大根堆存 (-耗時(shí), 編號(hào)) alive [False] * (n 1) now 0 for d, t, idx in tasks: heapq.heappush(heap, (-t, idx)) alive[idx] True now t if now d: neg_t, idx2 heapq.heappop(heap) alive[idx2] False now - -neg_t ans [idx for _, t, idx in tasks if alive[idx]] print(len(ans)) print(*ans) if __name__ __main__: main()Python 版本里heapq默認(rèn)是小根堆所以存-t取出時(shí)再取負(fù)得到真實(shí)耗時(shí)。整體邏輯和 C 一致。3.4 手工模擬一個(gè)完整樣例用下面這組數(shù)據(jù)來走一遍流程任務(wù)編號(hào)耗時(shí) t截止時(shí)間 d134225316447528排序后順序就是 1、2、3、4、5。一開始now 0堆為空。處理任務(wù) 1加入now 33 4合法。堆里現(xiàn)在是{3}。處理任務(wù) 2加入now 55 5合法。堆里是{3, 2}。處理任務(wù) 3加入now 66 6合法。堆里是{3, 2, 1}。處理任務(wù) 4加入now 1010 7超時(shí)。此時(shí)堆頂是任務(wù) 4耗時(shí) 4所以把任務(wù) 4 刪掉now 10 - 4 6。堆里剩下{3, 2, 1}。處理任務(wù) 5加入now 88 8合法。堆里現(xiàn)在是{3, 2, 2, 1}。最終堆中有 4 個(gè)任務(wù)分別是任務(wù) 1、2、3、5。按截止時(shí)間順序輸出就是1 2 3 5。驗(yàn)證一下任務(wù) 1完成于時(shí)刻 3截止 4合法任務(wù) 2完成于時(shí)刻 5截止 5合法任務(wù) 3完成于時(shí)刻 6截止 6合法任務(wù) 5完成于時(shí)刻 8截止 8合法。所以最優(yōu)軌跡就是 1 → 2 → 3 → 5答案 4。這里可以看到任務(wù) 4 雖然截止時(shí)間晚但耗時(shí)太長如果把它留下就必須刪掉任務(wù) 1最終總耗時(shí)反而更大。算法選擇刪除耗時(shí)最大的任務(wù)其實(shí)是在為后續(xù)任務(wù)留出更多空間。4. 常見問題與調(diào)試實(shí)錄4.1 排序的第二關(guān)鍵字要不要處理很多實(shí)現(xiàn)里只按截止時(shí)間升序排序相同截止時(shí)間的任務(wù)順序任意。這不會(huì)影響答案因?yàn)榉椿谪澬淖罱K選出的集合和數(shù)量是一樣的。不過有一個(gè)小細(xì)節(jié)如果相同截止時(shí)間耗時(shí)大的任務(wù)放在前面可能會(huì)導(dǎo)致它加入后又立刻被刪掉多一次堆操作如果把耗時(shí)小的放在前面操作會(huì)少一點(diǎn)。但復(fù)雜度上都是 (O(n \log n))差別不大。我有一次在本地對(duì)拍時(shí)發(fā)現(xiàn)兩種排序得到的軌跡編號(hào)不一樣但答案數(shù)量和可行性完全一致后來想明白是因?yàn)榇嬖诙鄠€(gè)最優(yōu)解。如果你希望輸出穩(wěn)定可以在排序時(shí)第二關(guān)鍵字按耗時(shí)升序或按編號(hào)升序這樣軌跡確定。4.2 為什么掃描時(shí)只判斷now d[i]就夠了這個(gè)問題我在學(xué)習(xí)的時(shí)候困惑了很久。因?yàn)楫?dāng)前已選任務(wù)里可能有截止時(shí)間比d[i]更早的任務(wù)如果now變大了會(huì)不會(huì)導(dǎo)致那些更早截止的任務(wù)超時(shí)答案是不會(huì)。因?yàn)樵趻呙柽^程中已選任務(wù)始終按截止時(shí)間升序排列新加入的任務(wù)一定排在末尾。更早的任務(wù)完成時(shí)刻不會(huì)因?yàn)楹竺娌迦胄氯蝿?wù)而改變。它們?cè)谧约罕患尤氲哪莻€(gè)時(shí)刻已經(jīng)驗(yàn)證過合法了所以后續(xù)只需要檢查新加入的這個(gè)最晚截止任務(wù)即可。這個(gè)性質(zhì)是“按截止時(shí)間排序”帶來的紅利。如果一開始沒有排序這里的正確性就不成立了。4.3 堆空時(shí)能不能pop代碼里只有在now d[i]時(shí)才進(jìn)入pop而這時(shí)剛剛push了當(dāng)前任務(wù)所以堆一定不為空。不要在最外層寫一個(gè)“如果堆非空才 pop”之類的邏輯那樣反而可能掩蓋真正的問題。我見過有人這樣寫if (now d) { if (!pq.empty()) { ... } }這個(gè)寫法雖然不會(huì) RE但會(huì)掩蓋一個(gè)邏輯漏洞如果堆是空的說明之前已經(jīng)出錯(cuò)了不該繼續(xù)往下跑。正確的做法是在該刪除的時(shí)候堆一定非空直接pop就好。4.4 輸出軌跡時(shí)“堆里有什么”不等于“順序是什么”這是我第一次寫這個(gè)題時(shí)犯的錯(cuò)。我直接把堆里剩下的任務(wù)編號(hào)pop出來當(dāng)作軌跡結(jié)果順序完全亂。因?yàn)槎阎槐ＷC能快速取出最大耗時(shí)元素并不維護(hù)截止時(shí)間順序。正確的輸出方式有兩種用alive標(biāo)記數(shù)組最后再遍歷一次按截止時(shí)間排好的任務(wù)數(shù)組輸出存活任務(wù)的編號(hào)或者把所有存活任務(wù)的編號(hào)收集后重新按照這些任務(wù)原來的截止時(shí)間排序再輸出。第一種更簡單也更好調(diào)試。記住你維護(hù)“當(dāng)前集合”用的是堆但輸出“軌跡”時(shí)要回到有序數(shù)組。4.5 用 DP 對(duì)拍驗(yàn)證貪心為了確保貪心算法不是碰巧過樣例我寫了一個(gè) (O(n^2)) 的 DP 用來對(duì)拍。DP 的狀態(tài)設(shè)計(jì)令dp[j]表示“處理完當(dāng)前前綴完成 j 個(gè)任務(wù)所需的最小累計(jì)耗時(shí)”并且保證這 j 個(gè)任務(wù)按截止時(shí)間升序排列時(shí)都合法。初始dp[0] 0其余為無窮大。按截止時(shí)間升序遍歷每個(gè)任務(wù)對(duì)每個(gè)任務(wù)做反向更新vectorlong long dp(n 1, LLONG_MAX / 4); dp[0] 0; for (auto task : tasks) { long long t task.t, d task.d; for (int j n; j 1; j--) { if (dp[j - 1] t d) { dp[j] min(dp[j], dp[j - 1] t); } } }最終最大的j滿足dp[j] INF就是最優(yōu)任務(wù)數(shù)。這個(gè) DP 的理解方式dp[j - 1]是完成前 j-1 個(gè)任務(wù)的最小耗時(shí)把當(dāng)前任務(wù)作為第 j 個(gè)任務(wù)放到底只要dp[j - 1] t d就說明它能在截止時(shí)間前完成。反向更新保證每個(gè)任務(wù)最多被選一次。對(duì)拍時(shí)隨機(jī)生成小規(guī)模數(shù)據(jù)分別跑貪心和 DP比較答案數(shù)量、合法性、以及最終輸出軌跡是否確實(shí)不超時(shí)。跑了幾萬組之后我才敢確信這個(gè)貪心是對(duì)的。5. 擴(kuò)展從“任務(wù)數(shù)量”到“加權(quán)收益”5.1 帶權(quán)任務(wù)調(diào)度的堆解法《學(xué)習(xí)軌跡》只要求最大化任務(wù)數(shù)量。如果把條件改成“每個(gè)任務(wù)還有一個(gè)收益 ( w_i )目標(biāo)是總收益最大”那刪除策略就要變了。此時(shí)按截止時(shí)間排序的思路不變但超時(shí)后要?jiǎng)h除的是“收益最小”的任務(wù)而不是耗時(shí)最大的任務(wù)。具體做法是維護(hù)一個(gè)小根堆堆內(nèi)存當(dāng)前已選任務(wù)的收益。每次嘗試加入新任務(wù)累加總耗時(shí)如果超時(shí)就從堆里彈出收益最小的任務(wù)并從總耗時(shí)里減去它的耗時(shí)。這樣可以保證在相同總耗時(shí)限制下保留的收益盡可能大。這個(gè)模型非常經(jīng)典很多任務(wù)調(diào)度題都是它的變體。5.2 “學(xué)習(xí)總時(shí)長最長”與“數(shù)量最多”的差別如果題目問的不是“最多能完成幾個(gè)任務(wù)”而是“在合法前提下最多能累計(jì)學(xué)習(xí)多長時(shí)間”那又是另一種趣味。這時(shí)候每個(gè)任務(wù)的收益就是它的耗時(shí)本身。用帶權(quán)調(diào)度的方法超時(shí)時(shí)刪除收益最小的任務(wù)也就是刪除耗時(shí)最短的任務(wù)。你會(huì)發(fā)現(xiàn)這個(gè)策略和“數(shù)量最多”恰好相反一個(gè)努力留下耗時(shí)短的任務(wù)一個(gè)努力留下耗時(shí)長但價(jià)值高的任務(wù)。同樣是反悔貪心不同的優(yōu)化目標(biāo)導(dǎo)致不同的刪除優(yōu)先級(jí)。這個(gè)對(duì)比非常值得自己推一遍能加深對(duì)“反悔貪心核心在于維護(hù)不變量”的理解。5.3 更進(jìn)一步的學(xué)習(xí)建議如果你把《學(xué)習(xí)軌跡》吃透了可以繼續(xù)看這些方向帶截止時(shí)間、耗時(shí)和收益的通用調(diào)度問題核心是排序 堆多臺(tái)機(jī)器并行學(xué)習(xí)的變體需要用多個(gè)堆或者可撤銷堆來維護(hù)依賴關(guān)系下的學(xué)習(xí)路徑規(guī)劃那就要結(jié)合拓?fù)渑判颉湫?DP 甚至反悔貪心一起考慮。算法競賽里很多題都是這樣表面上是“軌跡”“路徑”“規(guī)劃”剝開之后底層是一個(gè)經(jīng)典模型。學(xué)會(huì)從題目包裝里找到核心矛盾比背某個(gè)特定解法重要得多。6. 一點(diǎn)個(gè)人經(jīng)驗(yàn)這種“排序 反悔刪除”的貪心題我踩過最多次的坑不是想不到堆而是沒有想清楚“刪除哪個(gè)”背后的優(yōu)化目標(biāo)。只看任務(wù)數(shù)量時(shí)刪除耗時(shí)最大看總收益時(shí)刪除收益最小。不要死記一定要從“刪除一個(gè)任務(wù)后對(duì)后續(xù)狀態(tài)有什么影響”出發(fā)去推導(dǎo)。如果你也正在學(xué)貪心我建議拿到一道調(diào)度題先別急著寫代碼先回答三個(gè)問題第一固定選擇集合后最優(yōu)執(zhí)行順序是什么第二當(dāng)前維護(hù)的狀態(tài)里哪個(gè)量決定了后面的可行性第三被迫放棄一個(gè)任務(wù)時(shí)放棄標(biāo)準(zhǔn)應(yīng)該是什么這三個(gè)問題想明白代碼只是最后一步。最后分享一個(gè)調(diào)試小技巧寫對(duì)拍的時(shí)候不要只比較答案數(shù)量還要把貪心輸出的軌跡真正模擬執(zhí)行一遍逐個(gè)檢查每個(gè)任務(wù)的完成時(shí)間是否小于等于截止時(shí)間。很多反悔貪心實(shí)現(xiàn)看起來答案對(duì)但軌跡是錯(cuò)的問題往往出在輸出順序上。用alive標(biāo)記數(shù)組從有序數(shù)組里收集答案是最穩(wěn)妥的方式。