首页 > 代码库 > HDU - 4310 Hero(贪心)

HDU - 4310 Hero(贪心)

题意:无限生命,一点攻击力,和敌人对A(敌人只有攻击力和生命这两个属性),如何安排打到敌人的次序使得自己损失的生命最少。

攻击力高的可能血条很长,攻击力一般的可能血条很短,要先把相对比率高的先杀掉。

样例:2

   100 1

   101 100

 

   2

   100 1

   1 100

   第一个样例:10301  第二个:201

 1 //100 1
 2 //101 100 
 3 #include <iostream>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 struct Enemy{
 8     int dps;
 9     int hp;
10 }enemy[1010];
11 
12 bool cmp(Enemy a,Enemy b){
13     return a.dps*b.hp>b.dps*a.hp;//按比率排序 
14 }
15 
16 int main(){
17     int n;
18     while(cin>>n){
19         int sum=0,lost=0;
20         for(int i=0;i<n;i++){
21             cin>>enemy[i].dps>>enemy[i].hp;
22             sum+=enemy[i].dps;
23         }
24         sort(enemy,enemy+n,cmp);
25         for(int i=0;i<n;i++){
26             lost+=sum*enemy[i].hp;
27             sum=sum-enemy[i].dps;
28         }
29         cout<<lost<<endl;
30     }
31     return 0;
32 }

 

HDU - 4310 Hero(贪心)