[UVa 11729]Commando War

题解

由贪心的想法，很容易猜想到按$J$从大到小排序是对的。

如何证明呢？

我们拿两个任务出来单独考虑，因为显然某个任务是否完成与其他任务无关。

用反证法，我我们交换两个任务先后顺序。

我们假设任务$X$的$J$大于任务$Y$的$J$，由上，$X$在$Y$前安排。

那么分为两种情况，$X$比$Y$先完成和$Y$比$X$先完成，再用“相邻交换法”讨论一下，正确性很显然。

 1 #include <map>
 2 #include <set>
 3 #include <cmath>
 4 #include <ctime>
 5 #include <queue>
 6 #include <stack>
 7 #include <cstdio>
 8 #include <string>
 9 #include <vector>
10 #include <cstdlib>
11 #include <cstring>
12 #include <iostream>
13 #include <algorithm>
14 #define LL long long
15 #define Max(a, b) ((a) > (b) ? (a) : (b))
16 #define Min(a, b) ((a) < (b) ? (a) : (b))
17 using namespace std;
18 const int N =  1000;
19 
20 int n;
21 struct tt {
22     int b, j;
23 }a[N+5];
24 
25 bool comp(tt a, tt b) {
26     return a.j > b.j;
27 }
28 
29 int work() {
30     for (int i = 1; i <= n; i++)
31         scanf("%d%d", &a[i].b, &a[i].j);
32     sort(a+1, a+n+1, comp);
33     int ans = 0, last = 0;
34     for (int i = 1; i <= n; i++) {
35         last += a[i].b;
36         ans = Max(ans, last+a[i].j);
37     }
38     return ans;
39 }
40 
41 int main() {
42     int cnt = 0;
43     while ((~scanf("%d", &n)) && n) {
44         cnt ++;
45         printf("Case %d: %d
", cnt, work());
46     }
47     return 0;
48 }