题目 H. Fight Against Monsters

【题目链接】

现在有 n 只怪兽，每只怪兽有一个体力值 HPi 和一个攻击值 ATKi。
英雄需要同时和这 n 只怪兽进行战斗。
在每一秒，首先英雄会被当前未被打倒的所有怪兽攻击，受到与这些怪兽的攻击值之和等量的伤害。
然后他要选择一只未被打倒的怪兽进行攻击。对同一只怪物进行的第 i 次攻击能对其造成 i 点伤害。 当怪兽的体力值 ≤ 0 的时候就会倒下，当所有怪兽都被打倒时战斗立即结束。 英雄需要合理地进行攻击以使战斗过程中受到的伤害之和最小，请你求出这个伤害总量。

输入格式

第一行包含一个整数 T，表示有 T 组测试数据。
接下来依次描述 T 组测试数据。对于每组测试数据：
第一行包含一个整数 n，表示怪兽的数量。
接下来 n 行，每行包含两个整数 HPi,ATKi，表示每只怪兽的体力值和攻击值。

输出格式

对于每组测试数据，输出一行信息 “Case #x: y”（不含引号），其中 x 表示这是第 x 组测试数据， y 表示战斗过程中受到的伤害之和的最小值。

思路

要加long long ! 要加long long ! 要加long long !
贪心，记num表示打倒第 i 只怪兽需要的攻击次数，按照 num / atk 从小到大的顺序消灭怪兽是最优的。 证明只需要考虑交换相邻两只怪物不会使答案变优的充要条件，可以发现条件是传递的。
如果加结构体中定义flag=num/atk，然后按照flag排序，会由于flag的精度问题导致答案错误，所以在排序时通过交换二者分母即a/b=d/c就变成了a*c=b*d，从而避免精度问题。

#include<iostream>
#include<algorithm>
using namespace std;
typedef struct node
{
    int hp;
    int atk;
    int num;
}Node;
int fun(int k)
{
    int s = 1, count = 0;
    while (k > 0)
    {
        count++;
        k -= s;
        s++;
    }
    return count;
}
bool cmp(Node a, Node b)
{
    //return a.id<b.id;
    return a.num*b.atk < a.atk*b.num;
}
int main()
{
    int t;
    cin >> t;
    for (int i = 1; i <= t; i++)
    {
        int n;
        cin >> n;
        Node que[n];
        for (int i = 0; i < n; i++)
        {
            cin >> que[i].hp >> que[i].atk;
            que[i].num = fun(que[i].hp);
            //que[i].id = que[i].num / que[i].atk;
        }
        sort(que, que + n, cmp);
        long long int sum = 0, cnt = 0;
        for (int i = 0; i < n; i++)
        {
            cnt += que[i].num;
            sum += cnt * que[i].atk;
        }
        cout << "Case #" << i << ": ";
        cout << sum << endl;
    }
}