UVA11729 Commando War
题目链接
题意翻译
突击战
你有n个部下，每个部下需要完成一项任务。第i个部下需要你花Bj分钟交代任务，然后他就会立刻独立地、无间断地执行Ji分钟后完成任务。你需要选择交代任务的顺序，使得所有任务尽早执行完毕（即最后一个执行完的任务应尽早结束）。注意，不能同时给两个部下交代任务，但部下们可以同时执行他们各自的任务。
输入格式
输入包含多组数据，每组数据的第一行为部下的个数N(1<=N<=1000);以下N行每行两个正整数B和J（1<=B<=10000,1<=J<=10000),即交待任务的时间和执行任务的时间。输入结束标志为N=0。
输出格式
对于每组数据，输出所有任务完成的最短时间。
样例输入
3 2 5 3 2 2 1 3 3 3 4 4 5 5 0
样例输出
Case 1：8 Case 2：15
由 @Legends丶dream 提供翻译
输入输出样例
输入
3
2 5
3 2
2 1
3
3 3
4 4
5 5
0
输出
Case 1: 8
Case 2: 15
解题思路
在前面的人执行任务的时候，可以安排后面的人的任务，以此来达到节约时间的目的
排序+贪心
读入数据后对数据按照执行任务的时间从大到小排序
然后遍历循环记录所需的时间
#include <bits/stdc++.h> using namespace std; //部下结构体 struct buxia { int b;//安排任务时间 int j;//执行任务时间 }; //按照完成任务时间大到小排列 bool complare( buxia a, buxia b ) { return a.j>b.j; } int main() { int count = 0;//第几个样例 while ( true ) { int n; cin >> n; //输入n为0退出 if ( n==0 ) break; count++; buxia bx[n]; //读入 for ( int i=0; i<n; i++ ) { cin >> bx[i].b >> bx[i].j; } //根据完成任务的时间进行排序 sort( bx, bx+n, complare ); // for ( int i=0; i<n; i++ ) { // cout << bx[i].b << " " << bx[i].j << endl; // } //安排任务所需要的总时间 //到安排第i个人任务时所需要的安排任务时间 int time_b = 0; int ans = 0;//所有任务安排完执行完的总时间 for( int i=0; i<n; i++ ) { time_b += bx[i].b;//安排新任务 //安排完第i个任务后的第i人完成任务时的花费时间 //前i个所有任务完成的时间 //即判断安排完任务时，是否前面还有人在执行任务 //前面还在执行任务 到 执行完成所需的时间 //和 //新的任务安排到执行完的时间 //两个取较大者 ans = max( time_b+bx[i].j, ans ); } cout << "Case " << count << ": " << ans << endl; } }
