贪心-Fight Against Monsters

Fight Against Monsters题意一个英雄与多个怪兽对战怪兽先手每次对其英雄造成的伤害为目前存活的怪兽的伤害总和而英雄对同一只怪兽造成的伤害第一回合为1第二回合为2第三回合为3以此类推当怪兽血量小于等于0时该怪兽死亡问英雄打败怪兽后最低消耗多少血量。It is my great honour to introduce myself to you here. My name is Aloysius Benjy Cobweb Dartagnan Egbert Felix Gaspar Humbert Ignatius Jayden Kasper Leroy Maximilian. As a storyteller, today I decide to tell you and others a story about the hero Huriyyah, and the monsters.Once upon a time, citizens in the city were suffering from nnn powerful monsters. They ate small children who went out alone and even killed innocent persons. Before the hero appeared, the apprehension had overwhelmed the people for several decades. For the good of these unfortunate citizens, Huriyyah set off to the forest which was the main lair of monsters and fought with nnn fierce and cruel monsters. The health point of the iii-th monster was HPiHP_iHPi​, and its attack value was ATKiATK_iATKi​.They fought in a cave through a turn-based battle. During each second, the hero Huriyyah was attacked by monsters at first, and the damage was the sum of attack values of all alive monsters. Then he selected a monster and attacked it. The monster would suffer the damage of kkk (its health point would decrease by kkk) which was the times of attacks it had been came under. That is to say, for each monster, the damage of the first time that Huriyyah attacked it was 111, and the damage of Huriyyah’s second attack to this monster was 222, the third time to this monster was 333, and so on. If at some time, the health point of a monster was less than or equal to zero, it died. The hero won if all monsters were killed.Now, my smart audience, can you calculate the minimum amount of total damages our hero should suffer before he won the battle?InputThe input contains several test cases, and the first line is a positive integer TTT indicating the number of test cases which is up to 10310^3103.For each test case, the first line contains an integers n(1≤n≤105)n (1 \le n \le 10^5)n(1≤n≤105) which is the number of monsters. The iii-th line of the following nnn lines contains two integers HPiHP_iHPi​ and ATKi(1≤HPi,ATKi≤105)ATK_i (1 \le HP_i, ATK_i \le 10^5)ATKi​(1≤HPi​,ATKi​≤105) which describe a monster.We guarantee that the sum of nnn in all test cases is up to 10610^6106.OutputFor each test case, output a line containing Case #x: y, where xxx is the test case number starting from 111, and yyy is the minimum amount of total damages the hero should suffer.输出时每行末尾的多余空格不影响答案正确性样例输入231 12 23 333 12 21 3样例输出Case #1: 19Case #2: 14思路贪心计算每只怪兽需要攻击的次数用攻击的次数/该怪兽的攻击力来评价攻击该怪兽的性价比按从小到大顺序排列即需要攻击的次数越小该怪兽的攻击力越高该怪兽越先被击杀由于小数可能存在精度问题可以将分母乘上去·。 #includestdio.h #includecstring #includemath.h #define maxn 100010 #includealgorithm using namespace std; struct node{ long long hea;//血量 long long att;//攻击力 long long tem;//打败该怪兽需要攻击的次数 }list[maxn]; bool cmp(const node x,const node y) { return x.tem*y.atty.tem*x.att; } int main() { long long t,n,i,cout,sum,at,coutt,s,d; scanf(%lld,t);coutt0; while(t--) { scanf(%lld,n); for(at0,i1;in;i) { scanf(%lld%lld,list[i].hea,list[i].att); atlist[i].att; dlist[i].hea; s1;list[i].tem0; while(d0) { d-s; s; list[i].tem; } } sort(list1,list1n,cmp); for(sum0,i1;in;i) { cout1; while(list[i].hea0){ sumat; list[i].hea-cout; cout; } at-list[i].att; } coutt; printf(Case #%lld: %lld\n,coutt,sum); } return 0; }