日期：2026年10月29日
ZeroJudge 題目連結：p926.礦業調度 (Mining)
題目 pdf 檔連結：礦業調度 (Mining)
解題想法
每組測資第一列為兩個整數 $n ~(1 \leq n \leq 10^5), m ~(1 \leq m \leq 100)$，代表有 $n$ 座礦脈、共開採 $m$ 天；第二列有 $n$ 個正整數 $a_i ~(1 \leq a_i \leq 10^6)$，分別代表第 $i$ 座礦脈一開始每天可以開採的金礦。某一座礦脈開採一天之後，隔天可以開採的量會減 $1$。運輸金礦的成本與礦脈索引值有關，第 $i$ 座礦脈的運輸成本為 $i-1$。求這 $m$ 天的最大收益。
這題很適合用最大優先佇列解題。開一個最大優先佇列 $pq$，假設第 $i$ 座礦脈一開始每天可以開採的金礦減掉運輸成本之後大於 $0$，加入 pq。設定答案 $ans = 0$。接下來跑 while 迴圈，當開採天數 $m$ 還沒有歸零而且 $pq$ 還有資料時繼續執行，取出 $pq$ 之中的最大值 $v$，答案 $ans += v$，如果 $v > 1$，將 $v-1$ 加入 $pq$。跑完 while 迴圈之後印出 $ans$。
Python 程式碼
使用時間約為 57 ms，記憶體約為 18.8 MB，通過測試。
def solve():
import sys, heapq
result = []
data = sys.stdin.read().split()
ptr = 0
while ptr < len(data):
n = int(data[ptr]) # n 座礦脈
m = int(data[ptr + 1]) # 開採 m 天
ptr += 2
# 用最大優先佇列儲存各個礦脈目前的收益 = 産量 - 成本
pq = []
for i in range(1, n + 1):
v = int(data[ptr]) - (i - 1)
ptr += 1
if v > 0: # 收益大於 0 才放進來
heapq.heappush(pq, -v)
# 最多開採 m 天且 pq 要有資料
ans = 0 # 答案
while m > 0 and pq:
m -= 1
v = -heapq.heappop(pq)
ans += v
if v > 1:
heapq.heappush(pq, -(v - 1))
result.append(f"{ans:d}\n")
sys.stdout.write("".join(result))
if __name__ == "__main__":
solve()
