20111010 19:15 acm hdu 4070 War

题目网址http://acm.hdu.edu.cn/showproblem.php?pid=4070

比赛网址The 36th ACM/ICPC Asia Regional Fuzhou Site —— Online Contest

简单贪心，距离远的先繁殖。

排序一下，更新答案即可。

View Code

 1 #include<iostream>
 2 
 3 using namespace std;
 4 
 5 
 6 
 7 #define M 200005
 8 
 9 int T,n;
10 
11 struct node
12 
13 {
14 
15     int d,t;
16 
17 }d[M];
18 
19 bool cmp(node a,node b)
20 
21 {
22 
23     if (a.t!=b.t) return a.t>b.t;
24 
25     return a.d>b.d;
26 
27 }
28 
29 int main()
30 
31 {
32 
33     int i,j;
34 
35     scanf("%d",&T);
36 
37     for (int ca=1;ca<=T;ca++)
38 
39     {
40 
41         scanf("%d",&n);
42 
43         for (i=0;i<n;i++)
44 
45         {
46 
47             scanf("%d%d",&d[i].d,&d[i].t);
48 
49         }
50 
51         sort(d,d+n,cmp);
52 
53         int ans=0,tmp=0,time=0;
54 
55         for (i=0;i<n;i++)
56 
57         {
58 
59             time+=d[i].d;
60 
61             ans=max(time+d[i].t,ans);
62 
63         }
64 
65         printf("Case %d: %d\n",ca,ans);
66 
67     }
68 
69     return 0;
70 
71 }