Commando War UVA - 11729 突击战

题目链接

突击战

你有n个部下，每个部下需要完成一项任务。第i个部下需要你花Bi分钟交代任务，然后他会独立地、无间断地执行Ji分钟后完成任务。你需要选择交代任务的顺序，使得所有任务尽早执行完毕（即最后一个执行完的任务应尽早结束）。注意，不能同时给两个部下交代任务，但部下们可以同时执行他们各自的任务。

分析：贪心。交代任务是必须要做的，那么将执行时间最长的任务放在最前面最节省时间。（交换次序减少执行任务的总时间，交代任务总时间不变）；

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1000 +5;
struct Soldier{
	int b,j;
	bool operator < (const Soldier &rhs) const {
		return j > rhs.j;
	}
}s[N];

int main(int argc, char** argv) {
	int n, kase = 0;
	while( scanf("%d",&n) == 1 && n){
		for(int i = 0; i < n; i++)
			scanf("%d%d",&s[i].b, &s[i].j);
		sort(s, s+n);
		int ans = s[n-1].j + s[n-1].b;
		for(int i = n-2; i >= 0; i--){
			ans = max( s[i].j, ans);
			ans += s[i].b;
		} 
		printf("Case %d: %d\n",++kase,ans);
	}
	return 0;
}

 正向递推。

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1000 +5;
struct Soldier{
	int b,j;
	bool operator < (const Soldier &rhs) const {
		return j > rhs.j;
	}
}s[N];

int main(int argc, char** argv) {
	int n, kase = 0;
	while( scanf("%d",&n) == 1 && n){
		for(int i = 0; i < n; i++)
			scanf("%d%d",&s[i].b, &s[i].j);
		sort(s, s+n);
		int ans = 0, sum = 0; 
		for(int i = 0; i < n; i++){
			sum += s[i].b;
			ans = max(ans, sum+ s[i].j);
		} 
		printf("Case %d: %d\n",++kase,ans);
	}
	return 0;
}

 

输入格式：

输入包含多组数据，每组数据的第一行为部下的个数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