本文主要是介绍hdu3979_Monster，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这是一个解法很简单，但是需要仔细考虑的问题。开始的时候可能会认为是攻击力越高越先处理。但是仔细考虑之后贪心点不仅仅由攻击力决定，还要它的生命值同时决定。勇士在攻击一个怪兽的同时别的怪兽也在攻击勇士，他们的伤害也在叠加。所以优先消灭的怪兽有两个因素同时的决定即有怪兽的攻击力和生命值的比值决定，攻击和生命值比值高的怪兽需要先处理掉。同时要注意此题的结果的取值范围。最终的结果需要使用long long型的数据。
#include<iostream>
#include<algorithm>
using namespace std;
struct monster_type{int hp;int ack;
};struct monster_type monster[10002];bool cmp_h_a(monster_type a,monster_type b){return a.hp*b.ack<b.hp*a.ack;
}
//此处我们要的是
//注意数值的范围 选择变量的类型
int main()
{int T;scanf("%d",&T);for(int p=1;p<=T;p++){int n,m;//0<n<=10000 0<m<=100scanf("%d%d",&n,&m);for(int i=0;i<n;i++){scanf("%d%d",&monster[i].hp,&monster[i].ack);monster[i].hp =(monster[i].hp+m-1)/m;}sort(monster,monster+n,cmp_h_a);long long result=0;int sum=0;for(int i=0;i<n;i++){sum+=monster[i].hp;result+=(long long)sum*monster[i].ack;//printf("sum=%d result=%d\n",sum,result);}printf("Case #%d: %lld\n",p,result); }return 0;
}
这篇关于hdu3979_Monster的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
