ZeroJudge B231: 書

現有 N 本書需印刷裝訂。每一本書必須先印刷再裝訂。工廠有 N 台裝訂機但只有一台印刷機。印刷機同時只能印一本書，而且必需印完一本書後才能印下一本書。現給定每一本書的印刷時間和裝訂時間，請計算所有書最快要多久才能印刷裝訂完畢。

範例測資

範例輸入範例輸出
EOF 輸入，輸入第一行為 N，即書的數目 (1 <= N <= 1000)。
以下 N 行每行代表一本書，每行有兩個數字。第一個數字代表書的印刷時間，第二個數字代表書的裝訂時間，時間都介於 1 到 1000 之間。		輸出所有書最快印刷裝訂完畢的時間。
2
5 2
1 1
2
10 9
9 8		7
27

解題思路

使用 Pair<int, int> 來收資料，只是要將資料反過來存，印刷時間存在 second，裝訂時間則存在 first。收完資料之後要將 Pair 陣列進行排序，然後跑 For迴圈 從 N-1 到 0，要從「裝訂時間最大」的資料開始做處理。

設定兩個變數 ans 和 start，都預設為 0。每次進到 For迴圈 時，都要將 start += 目前資料的印刷時間，start 是指所有資料所需的印刷時間，因為印刷機只有一臺。然後要計算 start + 裝訂時間是多少，並且和目前的 ans 做最大值的比較，ans 就是每次的印刷總時間 + 現在的裝訂時間最大值。

範例程式碼－ZeroJudge B231: 書

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int N;
    while (cin >> N) {
        pair<int, int> dom[5000] = {};
        for (int i = 0; i<N; i++) cin >> dom[i].second >> dom[i].first;
        sort(dom, dom+N);
        int ans = 0, start = 0;
        for (int i = N-1; i>=0; i--) {
            start += dom[i].second;
            int tmp = start + dom[i].first;
            ans = max(tmp, ans);
        }
        cout << ans << "\n";
    }
}

//ZeroJudge B231
//Dr. SeanXD
標籤

相關文章

發佈留言