# APCS實作題2025年6月第3題：貪心闖關 > 日期：2025年6月26日 > 作者：王一哲 > [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=q838) <br /> ## 題目 ### 問題描述 小花參加一個搬沙包挑戰賽，關卡有 $n$ 個，編號由 $1$ ~ $n$，初始時，每個關卡有若干個沙包。 選手會選擇一個仍有沙包的關卡，將其所有的沙包搬至編號順序下一個仍有沙包的關卡，若選擇的關卡為當前仍有沙包的關卡中編號最大的，則把沙包搬出關卡即可。 沙包被搬完的關卡標示為完成，意即不會再有沙包被搬進此關卡，挑戰會持續進行直到所有關卡完成，或小花選手無法一次搬動當下任何關卡的所有沙包，小花一次可搬動的沙包上限為 $t$ 個。 每成功搬動 $w$ 個沙包則得 $w$ 分，小花打算採用以下貪心的策略完成挑戰，請計算小花的總分： - 選擇當前關卡中沙包最少的關卡，若有超過一個關卡有當前最少的沙包，則選擇編號最小的關卡 - 重複以上步驟直到挑戰結束 以測資一為範例： - 選擇關卡4，搬1個沙包到關卡5，得1分，關卡狀態更新為 (4 4 2 0 10 3) - 選擇關卡3，搬2個沙包到關卡5，得2分，關卡狀態更新為 (4 4 0 0 12 3) - 選擇關卡6，已經是當前仍有沙包的關卡中編號最大的，所以將沙包移出關卡就好，得3分，關卡狀態更新為 (4 4 0 0 12 0) - 選擇關卡1，搬4個沙包到關卡2，得4分，關卡狀態更新為 (0 8 0 0 12 0) - 選擇關卡2，搬8個沙包到關卡5，得8分，關卡狀態更新為 (0 0 0 0 20 0) - 所有關卡中沙包最少的為20個，超過小花一次能搬動的上限8個，所以挑戰結束，總分為 1+2+3+4+8=18 <br /> ### 輸入格式 第一行有兩個正整數 $n, t ~(1 \leq n \leq 3 \times 10^5, ~ 1 \leq t \leq 10^9)$，第二行有 $n$ 個正整數代表關卡初始的沙包數量，關卡初始沙包數不超過 $10^9$。 子題配分 - 20%：$1 \leq n \leq 100, ~ 1 \leq t \leq 1000$ - 80%：無額外限制 <br /> ### 輸出格式 輸出一個正整數代表小花的總分，保證總分不超過 $10^{15}$。 <br /> ### 範例一：輸入 ``` 6 8 4 4 2 1 9 3 ``` ### 範例一：正確輸出 ``` 18 ``` ### 範例二：輸入 ``` 5 4 4 4 3 2 1 ``` ### 範例一：正確輸出 ``` 10 ``` <br /><br /> ## Python 程式碼 ### 寫法1，線性搜尋下一個有沙包的關卡編號 使用時間約為 2.6 s，記憶體約為 76.1 MB，通過測試。 ```python= import heapq n, t = map(int, input().split()) # n 個關卡，最多一次搬 t 個沙包 stages = list(map(int, input().split())) # 每個關卡的初始沙包數量 pq = [(bag, idx) for idx, bag in enumerate(stages) if bag > 0] # (沙包數量, 關卡編號) heapq.heapify(pq) # 轉成最小優先佇列 score = 0 # 分數 while pq: # 如果 pq 有資料繼續執行 # 如果 pq 有資料，但是 stages[idx] 與 pq 最上方儲存的數量不相同，此關已變動，移除此項 while pq and stages[pq[0][1]] != pq[0][0]: heapq.heappop(pq) # 如果 pq 沒有資料，終止迴圈 if not pq: break # 從 pq 最上方取出沙包數量、關卡編號 bag, idx = heapq.heappop(pq) # 無法一次搬完，中止迴圈 if bag > t: break # 線性搜尋，找右邊第一個有沙包的關卡，這個步驟最慢 nxt = -1 for i in range(idx+1, n): if stages[i] > 0: nxt = i break stages[idx] = 0 # 原關卡歸零 if nxt != -1: # 有找到下一關 stages[nxt] += bag # 更新數量 heapq.heappush(pq, (stages[nxt], nxt)) # 推入新數量 score += bag # 更新分數 ### 結束 while 迴圈 ### print(score) # 印出分數 ``` <br /> ### 寫法2，用 SortedList 儲存有沙包的關卡編號，用 bisect 查詢指定的編號 理論上可行，但是 ZeroJudge 網站不支援 SortedList，因為 sortedcontainers 不是標準的函式庫。 ```python= import heapq, bisect from sortedcontainers import SortedList n, t = map(int, input().split()) # n 個關卡，最多一次搬 t 個沙包 stages = list(map(int, input().split())) # 每個關卡的初始沙包數量 pq, pos = [], SortedList() # (沙包數量, 關卡編號)，有沙包的位置 for idx, bag in enumerate(stages): if bag > 0: pq.append((bag, idx)) # (沙包數量, 關卡編號) pos.add(idx) # idx 加入 pos heapq.heapify(pq) # 轉成最小優先佇列 score = 0 # 分數 while pq: # 如果 pq 有資料繼續執行 # 如果 pq 有資料，但是 stages[idx] 與 pq 最上方儲存的數量不相同，此關已變動，移除此項 while pq and stages[pq[0][1]] != pq[0][0]: heapq.heappop(pq) if not pq: break # 如果 pq 沒有資料，終止迴圈 bag, idx = heapq.heappop(pq) # 從 pq 最上方取出沙包數量、關卡編號 if bag > t: break # 無法一次搬完，中止迴圈 stages[idx] = 0 # 此關數量歸零 score += bag # 更新分數 curr = bisect.bisect_left(pos, idx) # 從 pos 之中找 idx 的索引值 if curr < len(pos)-1: # 如果不是最後一項 nxt = pos[curr+1] # 下一個有沙包的關卡編號 stages[nxt] += bag # 更新數量 heapq.heappush(pq, (stages[nxt], nxt)) # 推入新數量 pos.discard(idx) # 從 pos 之中移除 idx ### 結束 while 迴圈 ### print(score) # 印出分數 ``` <br /><br /> ## C++ 程式碼 ### 寫法1，線性搜尋下一個有沙包的關卡編號 使用時間約為 0.1 s，記憶體約為 15.2 MB，通過測試。 ```cpp= #include <cstdio> #include <queue> #include <utility> #include <functional> #include <vector> typedef long long LL; using namespace std; int main() { int n, t; scanf("%d %d", &n, &t); // n 個關卡，最多一次搬 t 個沙包 vector<LL> stages (n); // 每個關卡的初始沙包數量 priority_queue<pair<LL, int>, vector<pair<LL, int>>, greater<pair<LL, int>>> pq; // (沙包數量, 關卡編號) for(int i=0; i<n; i++) { // 讀取 n 個關卡一開始的沙包數量 LL bag; scanf("%lld", &bag); stages[i] = bag; if (bag > 0) pq.push(make_pair(bag, i)); } LL score = 0; // 分數 while(!pq.empty()) { // 如果 pq 有資料繼續執行 // 如果 pq 有資料，但是 stages[idx] 與 pq 最上方儲存的數量不相同，此關已變動，移除此項 while(!pq.empty() && stages[pq.top().second] != pq.top().first) pq.pop(); if (pq.empty()) break; // 如果 pq 沒有資料，終止迴圈 // 從 pq 最上方取出沙包數量、關卡編號 LL bag = pq.top().first; int idx = pq.top().second; pq.pop(); if (bag > t) break; // 無法一次搬完，中止迴圈 stages[idx] = 0; // 原關卡歸零 score += bag; // 更新分數 // 線性搜尋找右邊第一個有沙包的關卡 int nxt = -1; for(int i=idx+1; i<n; i++) { if (stages[i] > 0) { nxt = i; break; } } if (nxt != -1) { // 有找到下一關 stages[nxt] += bag; // 更新數量 pq.push(make_pair(stages[nxt], nxt)); // 推入新數量 } } printf("%lld\n", score); // 印出分數 return 0; } ``` <br /> ### 寫法2，用 set 儲存有沙包的關卡編號，用 lower_bound 查詢指定的編號 速度反而比線性搜尋還慢，使用時間約為 0.4 s，記憶體約為 28.8 MB，通過測試。 ```cpp= #include <cstdio> #include <queue> #include <utility> #include <functional> #include <vector> #include <set> typedef long long LL; using namespace std; int main() { int n, t; scanf("%d %d", &n, &t); // n 個關卡，最多一次搬 t 個沙包 vector<LL> stages (n); // 每個關卡的初始沙包數量 priority_queue<pair<LL, int>, vector<pair<LL, int>>, greater<pair<LL, int>>> pq; // (沙包數量, 關卡編號) set<int> pos; // 有沙包的關卡 for(int i=0; i<n; i++) { // 讀取 n 個關卡一開始的沙包數量 LL bag; scanf("%lld", &bag); stages[i] = bag; if (bag > 0) { pq.push(make_pair(bag, i)); pos.insert(i); } } LL score = 0; // 分數 while(!pq.empty()) { // 如果 pq 有資料繼續執行 // 如果 pq 有資料，但是 stages[idx] 與 pq 最上方儲存的數量不相同，此關已變動，移除此項 while(!pq.empty() && stages[pq.top().second] != pq.top().first) pq.pop(); if (pq.empty()) break; // 如果 pq 沒有資料，終止迴圈 // 從 pq 最上方取出沙包數量、關卡編號 LL bag = pq.top().first; int idx = pq.top().second; pq.pop(); if (bag > t) break; // 無法一次搬完，中止迴圈 stages[idx] = 0; // 原關卡歸零 score += bag; // 更新分數 pos.erase(idx); // 移除 idx // 用 set 的二分搜尋法找右邊第一個有沙包的關卡 auto it = pos.lower_bound(idx); if (it != pos.end()) { // 如果不是最後一項 int nxt = *it; // 下一個有沙包的關卡編號 stages[nxt] += bag; // 更新數量 pq.push(make_pair(stages[nxt], nxt)); // 推入新數量 } } printf("%lld\n", score); // 印出分數 return 0; } ``` <br /><br /> --- ###### tags:`APCS`、`C++`、`Python`