Fight Against Monsters Gym - 102222H【贪心】

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N=1e5+5;
 4 typedef long long ll;
 5 struct m
 6 {
 7     int hp,atk,num;
 8 }mon[N];
 9 bool cmp(m a,m b)
10 {
11     return a.atk*b.num>b.atk*a.num;//排序的依据是被攻击的次数和攻击力的乘积
12 }
13 int n;
14 int main()
15 {
16     int t,cas=0;
17     scanf("%d",&t);
18     while(t--)
19     {
20         scanf("%d",&n);
21         ll ack=0,ans=0;
22         for(int i=1;i<=n;i++)
23         {
24             scanf("%d%d",&mon[i].hp,&mon[i].atk);
25             ack+=mon[i].atk;
26             int t=(int)sqrt(mon[i].hp*2.0)-1;
27             while((t+1)*t/2<mon[i].hp)
28                 t++;
29             mon[i].num=t;
30         }
31         sort(mon+1,mon+1+n,cmp);
32         for(int i=1;i<=n;i++)
33         {
34             ans+=(mon[i].num*ack);
35             ack-=mon[i].atk;
36         }
37         printf("Case #%d: %lld\n",++cas,ans);
38     }
39     return 0;
40 }