首页 > 代码库 > hdu 4040 (贪心算法)

hdu 4040 (贪心算法)

2024-10-20 09:43:02   208人阅读

这题是我们学校比赛的题目,因为当时参加精英组比赛,除了3个大二的其他都是大三大四的大神,就抱着打酱油的心态去了,结果真的打酱油了;

事后看看题目,确实有些题目以当前水平是可以做出来的,原因应该是 心态 以及 时间分配上的问题.

这题一直卡在题目什么意思上,还有一题 求前K大数的,那题最后想到用堆,但是不会写- -,忘了优先队列这个东西.所以很遗憾啊..

总而言之就是会的东西太少了哈...还需要好好加油;

这题的意思就是说每个细胞每秒只能产生一个噬菌体,无论这个细胞里面有多少噬菌体,然后攒齐一定数量的噬菌体就可以再花费一定的时间感染一个细胞..

很显然,最先找耗时最大的细胞感染,此时能产生的噬菌体总数最多,即可以在相同时间内感染最多的细胞.即采用贪心算法;

 1 #include<iostream> 2 #include<algorithm> 3 using namespace std; 4 #define maxn 100005 5  int max(int a,int b) 6 { 7     return a>b?a:b; 8 } 9 int n,T;10 struct node11 {12     int     d,t;13 }game[maxn];14 int cmp(node &a,node &b)15 {16     return a.t>b.t;17 }18 int main()19 {20     int cnt,i,j,ans,temp;21     scanf("%d",&T);22     cnt=1;23     while(T--){24         scanf("%d",&n);25         for(i=0;i<n;i++)26             scanf("%d%d",&game[i].d,&game[i].t);27         sort(game,game+n,cmp);28         ans=game[0].d+game[0].t;29         temp=game[0].d;30         for(int i=1;i<n;i++){  31             ans=max(ans,temp+game[i].d+game[i].t); //产生尽量多的噬菌体;,即判断是否需要额外花费感染某个细胞;.32             temp+=game[i].d; // 增加需要生产感染所需的噬菌体的时间;33         }  34         printf("Case %d: %d\n",cnt++,ans);35     }36     return 0;37 }

 

hdu 4040 (贪心算法)


联系
我们