【題解】ZeroJudge b231: TOI2009 第三題:書

題目敘述: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
分享本文 Share with friends