UVA 11729(贪心)

UVA 11729
训练指南 第一章 例2
贪心,把完成任务时间最长的优先进行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define ms(i, j) memeset(i, j, sizeof i)
const int MAXN = 1000 + 5;
struct data{
int b, j;
bool operator <(const data &y) const {
return j > y.j;
}
}d[MAXN];
int n, kase = 0;
void init() {
for (int i=1;i<=n;i++) scanf("%d%d", &d[i].b, &d[i].j);
sort(d+1, d+1+n);
}
void solve() {
int maxi = 0, tot = 0;
for (int i=1;i<=n;i++) {
tot += d[i].b;
maxi = max(maxi, tot+d[i].j);
}
printf("Case %d: %d\n", ++kase, maxi);
}
int main() {
while (scanf("%d", &n)==1&&n) init(), solve();
return 0;
}

------ 本文结束 ------