51Nod 1099 - 任务执行排序（贪心）

1099 任务执行顺序

基准时间限制：1 秒 空间限制：131072 KB 分值: 20 难度：3级算法题

有N个任务需要执行，第i个任务计算时占R[i]个空间，而后会释放一部分，最后储存计算结果需要占据O[i]个空间（O[i] < R[i]）。

例如：执行需要5个空间，最后储存需要2个空间。给出N个任务执行和存储所需的空间，问执行所有任务最少需要多少空间。

Input

第1行：1个数N，表示任务的数量。（2 <= N <= 100000)

第2 - N + 1行：每行2个数R[i]和O[i]，分别为执行所需的空间和存储所需的空间。(1 <= O[i] < R[i] <= 10000)

Output

输出执行所有任务所需要的最少空间。

Input示例

20

14 1

2 1

11 3

20 4

7 5

6 5

20 7

19 8

9 4

20 10

18 11

12 6

13 12

14 9

15 2

16 15

17 15

19 13

20 2

20 1

Output示例

135

【思路】

   很明显的贪心题，但是贪心策略不是很好想。我们要明确一种任务执行所耗空间最小的执行顺序，那么就先考虑两个任务a[1]，a[2] 运行内存和存储内存分别为r，o那么如果a[1]在前a[2]在后执行，所消耗的最大空间是max(a[1].o+a[2].r,a[1].r)同样的，如果a[2]在前，a[1]在后，所消耗的最大空间是max(a[2].o+a[1].r,a[2].r)我们根据这个式子对任务进行排序即可，空间消耗小的先执行。

#include<bits/stdc++.h>
using namespace std;

const int maxn = 100050;

int n;
struct node {
	int r, o;
}a[maxn];

bool cmp(node x1, node x2) {
	return max(x1.o + x2.r, x1.r) < max(x2.o + x1.r, x2.r);
}

int main() {
	while (scanf("%d", &n) == 1) {
		for (int i = 0; i < n; i++) {
			scanf("%d%d", &a[i].r, &a[i].o);
		}
		sort(a, a + n, cmp);
		int ans = a[0].r;
		int store = a[0].o;
		for (int i = 1; i < n; i++) {
			ans = max(ans, store + a[i].r);
			store += a[i].o;
		}
		printf("%d\n", ans);
	}
	return 0;
}