貪心闖關 題解｜APCS 2025 年 6 月中高級 第 3 題
前置知識
這題的核心（照題目一步一步做，兩個慢的動作各換一個資料結構）下面會從頭講；要先會的是這幾件事，同一個主題兩邊都有的，對照著讀會更快上手：
set當成「隨時能拿最小值」的容器：NTUCPC Guide〈Set 與 Map〉——要帶走的是「begin()永遠是最小的，insert／erase各 \(O(\log n)\)；元素要改值，就先刪舊的再放新的」；吳邦一《AP325》第 2 章「C++ 可供搜尋的容器（set／map）」一節（教材 PDF 第 57～61 頁；Python 版第 2 章）。- 鏈結串列：NTUCPC Guide〈Linked List〉——要帶走的是「用兩個陣列
prv[]、nxt[]記每個元素的前後是誰，拿掉一個元素只要改兩個值」；《AP325》第 3 章「串列鏈結」一節（教材 PDF 第 102～105 頁；Python 版第 3 章）。 pair與結構化綁定，以及整數溢位（語法書 2.9）。priority_queue（只有最後的「另一種做法」會用到）：NTUCPC Guide〈Heap〉；《AP325》第 4 章「優先佇列」一節（教材 PDF 第 121～123 頁；Python 版第 4 章（I）），例題 P-4-7 岳不群的併派問題 同樣是「每次拿最小的、合併後放回去」。
簡潔題意
\(n\) 個關卡排成一排，每關一開始有一些沙包。每一步挑「還有沙包、沙包最少（一樣少取編號最小）」的關卡：它的沙包數超過 \(t\) 就結束；否則得到沙包數的分數，把這一關的沙包全部搬到右邊最近、還有沙包的關卡（沒有就搬出賽場），這一關標示為完成、之後不再收沙包。求總分（\(n \le 3 \times 10^5\)、\(t\) 與每關沙包數 \(\le 10^9\)、總分不超過 \(10^{15}\)）。
依正確通過的測試資料筆數給分，其中：
- 子題組 1（\(20\) 分）：\(n \le 100\)、\(t \le 1000\)。
- 子題組 2（\(80\) 分）：無額外限制。
先拿下 20 分：照題目一步一步模擬
題目把規則寫得很清楚，照做就好：用 bags[i] = 0 代表關卡 \(i\) 已完成；每一步掃一遍找最小（一樣少取編號小的，所以用 < 不用 <=）、沒得挑或最小的也超過 \(t\) 就結束、往右掃找第一個還有沙包的關卡把沙包加過去。
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 300000;
int n;
long long t, bags[MAX_N + 1]; // bags[i] = 0 代表關卡 i 已完成
int main() {
cin >> n >> t;
for (int i = 1; i <= n; i++) cin >> bags[i];
long long score = 0;
while (true) {
int pick = 0; // 0 = 還沒找到
for (int i = 1; i <= n; i++) { // 找沙包最少的關卡；一樣少取編號最小
if (bags[i] > 0 && (pick == 0 || bags[i] < bags[pick])) pick = i;
}
if (pick == 0 || bags[pick] > t) break; // 全部完成，或最少的也搬不動
score += bags[pick];
int j = pick + 1;
while (j <= n && bags[j] == 0) j++; // 右邊最近、還有沙包的關卡
if (j <= n) bags[j] += bags[pick]; // 找不到就是搬出賽場，什麼都不用做
bags[pick] = 0;
}
cout << score << endl;
return 0;
}
每一步最多掃兩遍、最多 \(n\) 步，\(O(n^2)\)：\(n \le 100\) 時不到 \(10^4\)，子題組 1 的 \(20\) 分穩穩到手；\(n = 3 \times 10^5\) 是 \(9 \times 10^{10}\)，本站實測超過 \(30\) 秒都跑不完。
沙包會越合併越多，最多 \(n \times 10^9 = 3 \times 10^{14}\)，總分最多 \(10^{15}\)，兩者都超過 int，一律 long long。
從 20 分到 100 分：兩個慢的動作各找一個資料結構
\(20\) 分版每一步有兩件 \(O(n)\) 的事，各換一個工具：
- 找沙包最少的關卡：把所有還有沙包的關卡用
(沙包數, 編號)放進set<pair<long long, int>>，pair先比沙包數、再比編號，所以*alive.begin()正好是「最少、一樣少取編號最小」。某一關的沙包數變了（收到別關搬來的沙包），set裡的元素不能直接改，要先erase舊的pair、再insert新的。 - 找右邊最近還有沙包的關卡：完成的關卡不會再有沙包，所以把它從一條「還有沙包的關卡」串列拿掉就好——
nxt[i]、prv[i]記左右鄰居，拿掉 \(i\) 時讓左右鄰居直接相連（nxt[prv[i]] = nxt[i]、prv[nxt[i]] = prv[i]），之後查nxt[i]永遠是 \(O(1)\)。用n + 1代表「右邊沒有了，搬出賽場」（圖 1）。
為什麼不乾脆 while (done[j]) j++ 往右找？完成的關卡會越積越多，右邊那一段完成的關卡每次都要重新跨過一遍——左半邊的關卡一關一關搬、中間一大段都已完成時，每一步都要跨過十幾萬格，\(n = 3 \times 10^5\) 本站實測 \(11\) 秒。串列把「跨過去」這件事一次做完，之後永遠一步到位。
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 300000;
int n;
long long t, bags[MAX_N + 2];
int nxt[MAX_N + 2]; // nxt[i] = i 右邊最近、還有沙包的關卡（n + 1 代表沒有了）
int prv[MAX_N + 2]; // prv[i] = i 左邊最近、還有沙包的關卡（0 代表沒有了）
int main() {
cin >> n >> t;
set<pair<long long, int>> alive; // (沙包數, 編號)：最前面就是「最少、一樣少取編號最小」
for (int i = 1; i <= n; i++) {
cin >> bags[i];
alive.insert({bags[i], i});
nxt[i] = i + 1;
prv[i] = i - 1;
}
long long score = 0;
while (!alive.empty()) {
auto [w, i] = *alive.begin(); // 沙包最少的關卡
if (w > t) break; // 連最少的都搬不動，挑戰結束
alive.erase(alive.begin());
score += w;
int j = nxt[i]; // 沙包要搬去的關卡
nxt[prv[i]] = j; // 把 i 從串列拿掉：左右鄰居直接相連
prv[j] = prv[i];
if (j <= n) { // j = n + 1 就是搬出賽場
alive.erase({bags[j], j}); // j 的沙包數要變了：先拿掉舊的紀錄
bags[j] += w;
alive.insert({bags[j], j});
}
}
cout << score << endl;
return 0;
}
每一步 set 的操作最多三次、串列 \(O(1)\)，最多 \(n\) 步，\(O(n \log n)\)，\(n = 3 \times 10^5\) 本站實測 \(0.5\) 秒。nxt、prv 多開兩格：prv[1] = 0、nxt[n] = n + 1 當作兩端的「沒有了」，拿掉第 \(1\) 關或第 \(n\) 關時不用特判。
測過再交：範例沒有「恰好等於 \(t\)」
範例 1 有合併、範例 2 全部搬出賽場，但沒有一步的沙包數剛好等於 \(t\)，也沒有「一開始就搬不動」、「好幾關一樣少」、「合併之後超過 \(t\)」的情況，更沒有大到會讓 int 溢位或讓 \(O(n^2)\) 跑不完的測資。
| 輸入 | 正確輸出 | 這一筆在測什麼 |
|---|---|---|
1 5／5 |
5 |
沙包數恰好等於 \(t\) 搬得動，是 > 不是 >= |
2 3／4 4 |
0 |
一開始就沒有關卡搬得動 |
3 10／2 2 2 |
8 |
一樣少取編號最小：先搬關卡 \(1\) 到關卡 \(2\)，再搬關卡 \(3\) 出賽場，最後關卡 \(2\) 的 \(4\) 個出賽場 |
3 5／3 3 3 |
6 |
關卡 \(2\) 合併成 \(6\) 之後超過 \(t\)：結束，不是跳過它繼續 |
| 用程式造：\(n = 300000\)、\(t = 10^9\)，每關都是 \(10^9\) | 150000000000000 |
兩關合併就是 \(2 \times 10^9\)，沙包數與總分都超過 int |
| 用程式造：\(n = 300000\)、\(t = 5 \times 10^8\)，前 \(150000\) 關是 \(300000, 299999, \ldots, 150001\)，接著 \(149999\) 關都是 \(1\)，最後一關 \(10^9\) | 33751466824 |
中間那一大段先搬完，左半邊再一關一關往右搬：用 while 往右找下一關的版本本站實測 \(11\) 秒 |
六筆都親眼看過正確，這題就穩了。
另一種做法：`priority_queue` 加「過期的紀錄跳過」
拿最小值也可以用 priority_queue（小的在上面要用 greater），但它不能像 set 那樣把舊的紀錄刪掉。做法是不刪：某一關收到沙包時直接把新的 (新沙包數, 編號) 推進去，舊的留在裡面；之後從頂端拿出來的紀錄，如果那一關已經完成、或沙包數跟現在的不一樣，就是過期的，跳過。每一關最多被推進去「初始一次 ＋ 收到沙包的次數」，總量還是 \(O(n)\)。
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 300000;
int n;
long long t, bags[MAX_N + 2];
int nxt[MAX_N + 2], prv[MAX_N + 2];
bool done[MAX_N + 2];
int main() {
cin >> n >> t;
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
for (int i = 1; i <= n; i++) {
cin >> bags[i];
pq.push({bags[i], i});
nxt[i] = i + 1;
prv[i] = i - 1;
}
long long score = 0;
while (!pq.empty()) {
auto [w, i] = pq.top();
pq.pop();
if (done[i] || w != bags[i]) continue; // 過期的紀錄：關卡已完成，或沙包數早就變了
if (w > t) break;
score += w;
done[i] = true;
int j = nxt[i];
nxt[prv[i]] = j;
prv[j] = prv[i];
if (j <= n) {
bags[j] += w;
pq.push({bags[j], j}); // 舊的 (舊沙包數, j) 留在裡面，之後拿到會被跳過
}
}
cout << score << endl;
return 0;
}
兩種都是滿分，本站實測 \(0.2\) 秒。priority_queue 版快一點、但多了「判斷過期」這一行，忘了寫就會拿到舊的沙包數（見常犯錯誤）；set 版直接刪舊的，沒有這個坑。
常犯錯誤
priority_queue版沒跳過過期的紀錄（只檢查完成了沒）：範例 1 印14、範例 2 印14——關卡收到沙包之前的舊紀錄先被拿出來，用的是舊的沙包數。set版改沙包數時沒先刪舊的pair：舊的紀錄還在，同一關會被搬兩次；範例 1 印22。- 沙包數用
int：兩個範例都過，計分測資掛 \(4\) 筆；自測表第 5 列合併後 \(2 \times 10^9\) 就溢位。總分用int：兩個範例都過，計分測資掛 \(10\) 筆。 - 沙包搬去 \(i + 1\)，不管它完成了沒：範例 1 印
21、範例 2 印13。 - 沙包數等於 \(t\) 就結束（
>=）：範例 1 印10、範例 2 印6；自測表第 1 列印0。 - 用
while一格一格往右找下一關：兩個範例都過，計分測資掛 \(3\) 筆（本站實測 \(14\) 秒，超時）；自測表第 6 列本站實測 \(11\) 秒。 - \(20\) 分版硬交：\(n = 3 \times 10^5\) 的計分測資掛 \(12\) 筆（超時）。