Fight Against Monsters

Fight Against Monsters

题意：

• 勇士打怪兽，怪兽有HP(血量)，ATK(攻击值)。勇士每次只能攻击一只怪兽，但是勇士攻击时，会受到所有的怪兽攻击。勇士每一次对怪兽的攻击值是勇士攻击这只怪兽的次数。假如怪兽的血量为0，则怪兽被消灭。勇士每一次受到的伤害是所有怪兽的攻击总和。输出勇士打败所有怪兽受到的最小伤害值。

思路：

• 为了勇士受到的伤害总值最小那么就意味着伤害值大的要先被消灭(因为每一次受到的伤害是所有怪兽攻击的总值，所以要将攻击值大的尽量少加)。但是问题又来了，只要满足攻击值大的先消灭吗？假如怪兽1的参数分别是,怪兽2的参数分别是；只考虑攻击值的话那先消灭怪兽2，但是先消灭怪兽1最后的总值更小。所以我们要先打那些攻击力大，攻击次数少的怪兽。
• 勇士击败怪兽的次数 / 怪兽的攻击值 从小到大排序

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int M=1e5+10;
const double ESp=1e-7;
struct node
{
    int HP;//血量
    int ATK;//攻击值
    int at;//需要被消灭的次数
}p[M];
ll sum[M];
bool cmp(node a,node b)
{
    return a.at*b.ATK<a.ATK*b.at;//勇士击败怪兽的次数 / 怪兽的攻击值 从小到大排序
}
int main( )
{
    int t,n;
    int m=0;
    scanf("%d",&t);
    while(t--)
    {
        m++;
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
            scanf("%d%d",&p[i].HP,&p[i].ATK);
            int c=2*p[i].HP;
            double x=(sqrt(1.0+4.0*c)-1)/2;//计算每只怪兽被消灭需要攻击的次数
            if(x- (double)((int)x) < ESp)//判断x是否是整数
            {
                int k=(int)x;
                p[i].at=k;
            }
            else
            {
                int k=(int)x;
                k=k+1;
                p[i].at=k;
            }
        }
        sort(p,p+n,cmp);
        sum[n-1]=p[n-1].ATK;
        for(int i=n-2;i>=0;i--)
        {
            sum[i]=sum[i+1]+p[i].ATK;
        }
        ll ans=0;
        for(int i=0;i<n;i++)
        {
            ans+=sum[i]*p[i].at;
        }
        cout<<"Case #"<<m<<": "<<ans<<endl;
    }
    return 0;
}