突击战[Commando War,UVa11729]

题目描述

你有N个部下，每个部下需要独立完成一项任务。第i个部下需要你花费Bi分钟交代任务，然后他会立刻独立、无间断地执行Ji分钟后完成任务。你需要选择交代任务的顺序，使得所有任务尽早执行完毕（即最后一个执行完的任务应尽早结束）。

注意，不能同时给两个部下交代任务，但部下们可以同时执行他们各自的任务。

输入格式

输入包含多组数据。

每组数据的第一行为部下的个数N，（1≤N≤1000）

接下来N行，每行两个用空格隔开的正整数B和J，分别代表第i个部下交代任务花费的时间Bi和执行任务的时间Ji.（1≤B,J≤10000）

当输入为单独的一行“0”时，表示输入结束

输出格式

对于每组数据，输出所有任务完成的最短时间。输出格式为’Case X: Y‘。X是数据编号，Y是所有任务完成的最短时间。

输入输出样列

输入样例1：复制

3 
2 5 
3 2 
2 1 
3 
3 3
4 4
5 5 
0

输出样例1：复制

Case 1: 8
Case 2: 15

AC代码：

#include<bits/stdc++.h>
using namespace std;
struct P{
	int b,j;	//b:交代时间  j:完成任务的时间 
}a[100005];
int cmp(P a,P b){
    if(a.j!=b.j)	return a.j>b.j;	//完成时间最长的先交代 
    return a.b<b.b;	//交代时间最短的先交代 
}
int ans;
int main(){
	int n;
	while(cin>>n&&n){
		ans++;
		//输入 
		for(int i=1;i<=n;i++)	cin>>a[i].b>>a[i].j;
		sort(a+1,a+n+1,cmp);
		int cnt=0;
		for(int i=1;i<=n;i++){
			cnt+=a[i].b;
		}
		cnt+=a[n].j; 
		cout<<"Case "<<ans<<": "<<cnt<<endl;
	}
    return 0;
}