題目敘述：https://zerojudge.tw/ShowProblem?problemid=b231
解題想法：Greedy、工作排程
- 題目給定 n 本書的印刷時間和裝訂時間，要計算最快能印刷裝訂完所有書的時間。
- 工廠有 n 台裝訂機，但只有一台印刷機，不管哪一本書先印，印刷機需要做工的時間都一樣。想要縮短總工時，最好先印裝訂時間較長的書。
- 把每一本書的 {裝訂時間，印刷時間} 丟進priority_queue，會自動依裝訂時間由長到短排序。
- cpt：紀錄累計花費的印刷時間 (cumulative print time)
- 每印完一本書，比較「cpt + 該書的裝訂時間」是否超過 ans。
#include <iostream>
#include <queue>
using namespace std;
int main(){
int n, p, b;
priority_queue <pair<int, int> > pq;
while (cin >> n){
for (int i = 0; i < n; i++){
cin >> p >> b;
pq.push(make_pair(b, p));
}
int cpt = 0; //累計花費的印刷時間
int ans = 0;
while (!pq.empty()){
cpt += pq.top().second;
ans = max(ans, cpt + pq.top().first);
pq.pop();
}
cout << ans << "\n\n";
}
return 0;
}
Python code (credit: Amy Chou)
while True:
try:
n = int(input())
lst = []
for _ in range(n):
p, b = map(int, input().split())
lst.append((b, p))
lst.sort(key = lambda x: (x[0], x[1]))
cpt = 0 #累計花費的印刷時間
ans = 0
while len(lst):
tp = lst.pop()
cpt += tp[1]
ans = max(ans, cpt + tp[0])
print(ans)
print()
_ = input() #兩筆測資之間有一空白列
except:
break