FJUT-1864
Hero
Problem Description
When playing DotA with god-like rivals and pig-like team members, you have to face an embarrassing situation: All your teammates are killed, and you have to fight 1vN.
There are two key attributes for the heroes in the game, health point (HP) and damage per shot (DPS). Your hero has almost infinite HP, but only 1 DPS.
To simplify the problem, we assume the game is turn-based, but not real-time. In each round, you can choose one enemy hero to attack, and his HP will decrease by 1. While at the same time, all the lived enemy heroes will attack you, and your HP will decrease by the sum of their DPS. If one hero's HP fall equal to (or below) zero, he will die after this round, and cannot attack you in the following rounds.
Although your hero is undefeated, you want to choose best strategy to kill all the enemy heroes with minimum HP loss.
Input
The first line of each test case contains the number of enemy heroes N (1 <= N <= 20). Then N lines followed, each contains two integers DPSi and HPi, which are the DPS and HP for each hero. (1 <= DPSi, HPi <= 1000)
Output
Output one line for each test, indicates the minimum HP loss.
SampleInput
1
10 2
2
100 1
1 100
SampleOutput
20
201
翻译(机翻)
英雄
问题描述
当你和上帝一样的对手和猪一样的队员玩DotA时，你必须面对一个尴尬的局面：你所有的队友都被杀了，你必须和1vN战斗。
游戏中的英雄有两个关键属性，生命值（HP）和每击伤害（DPS）。你的英雄几乎有无限的生命，但只有1点。
为了简化问题，我们假设游戏是基于回合的，但不是实时的。每轮可以选择一个敌方英雄进行攻击，其生命值降低1。同时，所有活着的敌方英雄都会攻击你，你的生命值会减少他们的DPS之和。如果一个英雄的生命值等于（或低于）0，他将在本回合后死亡，并且不能在接下来的回合中攻击你。
虽然你的英雄是不败的，但是你要选择最好的策略以最小的生命损失杀死所有的敌人英雄。
输入
每个测试用例的第一行包含敌人英雄的数量N（1<=N<=20）。接着是N行，每行包含两个整数DPSi和HPi，这是每个英雄的DPS和HP。（1<=DPSi，HPi<=1000）
输出
每次测试输出一行，表示最小HP损失。
样本输入
1
10 2
2
100 1
1 100
样本输出
20
201
#include<iostream>
#include<algorithm>
using namespace std;
struct hero{//结构体来存敌人的dps和hp
int dps;
int hp;
};
int cmp(hero x,hero y)
{
return 1.0*x.dps/x.hp<1.0*y.dps/y.hp;//让每滴血的输出从小到大排序
}
int main(){
int n;
while(cin>>n){
hero enemy[n];
for(int i=0;i<n;i++){
cin>>enemy[i].dps>>enemy[i].hp;
}
sort(enemy,enemy+n,cmp);//排序
int sum=0;
for(int i=n-1;i>=0;i--){
sum=sum+enemy[i].dps*enemy[i].hp;//打死一个敌人要消耗的血量
for(int j=0;j<i;j++){
sum=sum+enemy[j].dps*enemy[i].hp;//同一回合其他敌人的伤害
}
}
cout<<sum<<endl;//输出
}
return 0;
}贪心思想，要注意不应先打dps高的敌人，而是dps/hp高的敌人。
