2011-10-10 19:15 acm hdu 4070 War
7175 ワード
タイトルURL http://acm.hdu.edu.cn/showproblem.php?pid=4070
試合サイトThe 36th ACM/ICPC Asia Regional Fuzhou Site —— Online Contest
単純で欲張りで、距離の遠い先繁殖.
並べ替えて、答えを更新すればいいです.
View Code
試合サイト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
",ca,ans);
66
67 }
68
69 return 0;
70
71 }