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
| Sample Input(s) | Sample Output(s) |
|---|---|
| EOF input, with the first line of input containing N, the number of books (1 <= N <= 1000). The following N lines each represent a book, with each line containing two numbers. The first number represents the printing time of the book, and the second number represents the binding time of the book. The times are between 1 and 1000. | Output the minimum amount of time required to print and bind all the books. |
| 2 5 2 1 1 2 10 9 9 8 | 7 27 |
Thought Process
使用 Pair<int, int> 來收資料，只是要將資料反過來存，印刷時間存在 second，裝訂時間則存在 first。收完資料之後要將 Pair 陣列進行排序，然後跑 For迴圈 從 N-1 到 0，要從「裝訂時間最大」的資料開始做處理。
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