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