C/C++每天小练（五）——突击战

C/C++每日小练（五）——突击战

突击战

你有n个部下，每个部下需要完成一项任务。第i个部下需要你花Bi分钟交代任务，然后他会独立地、无间断地执行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

解：这是一个简单地贪心算法的应用——执行时间较长的任务先交代（选择两个任务执行时，顺序不同而导致总时间不同，在讨论选择两个任务哪个先执行的问题上，可以看出，由于两个任务交代的时间B是固定的，所以仅仅比较两个任务的执行时间J即可），所以要按照J从小到大的顺序给各个任务排序，然后依次交代～

Code：

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

struct Job {
	int j, b;
	bool operator < (const Job& x) const {		//运算符重载，要加上const～～
		return j > x.j;
	}
};

int main() {
	int n, b, j, count = 1;
	while(scanf("%d", &n)==1 && n) {
		vector<Job> v;
		for(int i = 0; i < n; i++) {
			scanf("%d%d", &b, &j);
			v.push_back((Job){j, b});
		}
		sort(v.begin(), v.end());										//使用Job类自己的<运算符排序
		int s = 0;
		int ans = 0;
		for(int i = 0; i < n; i++) {
			s += v[i].b;
			ans = max(ans, s+v[i].j);
		}
		printf("Case %d: %d\n", count++, ans);
	}
	return 0;
}

运行结果：