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;
}