b231 - TOI2009 第三題：書
題目描述
題目要求計算 n 本書的最小完成時間，其中每本書需要先印刷後裝訂。工廠只有一台印刷機和 n 台裝訂機。印刷必須依序進行，而裝訂可以並行進行。給定每本書的印刷時間和裝訂時間，求出完成所有書所需的最短時間。
解題思路
本題可以使用貪心策略解決。首先，按照裝訂時間降序排序書籍。然後，模擬印刷和裝訂的過程。
- 印刷機按照排序後的順序依次印刷書籍。
- 每本書印刷完成後，立即分配給一台空閒的裝訂機進行裝訂。
- 記錄完成所有書籍所需的總時間。
排序的目的是為了讓裝訂時間長的書籍先被裝訂，這樣可以最大程度地利用裝訂機，減少印刷機的等待時間。
複雜度分析
- 時間複雜度: O(n log n)
- 空間複雜度: O(n)
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
int n;
struct c{
int x;
int y;
};
bool cmp(c xx,c yy){
if(xx.y>yy.y){
return 1;
}
else if(xx.y==yy.y){
if(xx.x>yy.x){
return 1;
}
}
return 0;
}
int main(){
while(cin >> n){
c a[n];
int xt=0,ans=0;//總印刷時間,ans
for(int i=0;i<n;++i){
cin >> a[i].x >> a[i].y;
}
sort(a,a+n,cmp);
for(int i=0;i<n;++i){
xt+=a[i].x;
if(ans<xt+a[i].y)ans=xt+a[i].y;
}
cout << ans << "\n";
}
}