2016HUAS_ACM暑假集训2K - Hero(英雄)

这也属于一个贪心题。关键是排序的依据。

这题排序的依据是敌人的伤害/血量(DPS/HP),不难证明,当这个比值相同时,不论先解决谁效果是相同的。思路大部分在注释里。

题目大意:

  假设你的血量无限,但是你的伤害每次只有1点。现在你有N个敌人,给出他们的血量和伤害,要你在损失血量最少的情况下,解决所有敌人。

样例输入:(第一行整数N指有N个敌人,后面N行输入对应敌人的血量和伤害)

1

10 2

2

100 1

1 100

样例输出:

20

201

#include<iostream>
#include<algorithm>
using namespace std;
struct DOTA//保存敌军的血量和伤害
{
double HP,DPS;
}; bool comp(DOTA a,DOTA b)//按照(伤害)/(血量)进行降序排序。即优先解决伤害高、血量少的
{
return a.DPS/a.HP>b.DPS/b.HP;
} int main()
{
int n,i;
DOTA hero[];
while(cin>>n)
{
double lose=,harm=;
for(i=;i<n;i++)
{
cin>>hero[i].HP>>hero[i].DPS;
harm+=hero[i].DPS;//第一次受到的总伤害
}
sort(hero,hero+n,comp);
for(i=;i<n;i++)
{
lose+=harm*hero[i].HP;//把每次丢失的血量进行累加
harm-=hero[i].DPS;//解决掉一个后对应的总伤害要减掉
}
cout<<lose<<endl;
}
return ;
}
上一篇:[WPF]如何使用代码创建DataTemplate(或者ControlTemplate)


下一篇:UGUI 滚动视图