ZeroJudge B231: Book

There are N books that need to be printed and bound. Each book must first be printed and then bound. The factory has N-binding machines but only one printing machine. The printing machine can only print one book at a time, and it must complete printing one book before it can start printing the next one. Given the printing time and binding time for each book, calculate the minimum amount of time required to print and bind all the books.

Sample Inputs/Outputs

Thought Process

Use Pair to store the data, but store the data in reverse: the printing time should be stored in second, and the binding time should be stored in first. After collecting the data, sort the array of pairs. Then, run a for loop from N-1 to 0, starting with the data that has the maximum binding time.

Set two variables, ans and start, both initialized to 0. Each time you enter the for loop, increment start with the printing time of the current book. start represents the total printing time required so far since there is only one printing machine. Then, calculate start + binding time and compare it with the current ans to take the maximum value. ans will be the maximum of the total printing time plus the current binding time.

Sample Code－ZeroJudge B231: Book

#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