贪心的策略
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 ",++cas,ans); 38 } 39 return 0; 40 }