hdu 3979(贪心）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3979

思路：我们可以从2只monster入手，假设a1和a2的总攻击力为v,杀死a1需要时间t1,a1的atk为c1;杀死a2的时间为t2,a2的atk为c2;如果先攻击a1,那么受伤值为t1*v+(v-c1)*t2;

如果先攻击a2,那么受伤值为t2*v+(v-c2)*t1;

假使t1*v+(v-c1)*t2<t2*v+(v-c2)*t1;即t1*c2<t2*c1;直接根据这个排序即可。

View Code

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 using namespace std;
 7 #define MAXN 10000+10
 8 typedef __int64 ll;
 9 int n,m;
10 struct Node {
11     int hp,atk;
12 }node[MAXN];
13 
14 int cmp(const Node &p,const Node &q){
15     int x=(int)ceil(p.hp*1.0/m);
16     int y=(int)ceil(q.hp*1.0/m);
17     return x*q.atk<y*p.atk;
18 
19 }
20 
21 int main(){
22     int _case,t=1;
23     scanf("%d",&_case);
24     while(_case--){
25         scanf("%d%d",&n,&m);
26         for(int i=1;i<=n;i++){
27             scanf("%d%d",&node[i].hp,&node[i].atk);
28         }
29         sort(node+1,node+1+n,cmp);
30         printf("Case #%d: ",t++);
31         ll ans=0,tmp=0;
32         for(int i=1;i<=n;i++){
33             tmp+=(ll)ceil(node[i].hp*1.0/m);
34             ans+=tmp*(ll)node[i].atk;
35         }
36         printf("%I64d\n",ans);
37     }
38     return 0;
39 }
40 
41 
42