算法设计与分析 4.2 洪尼玛与网络攻防战

题目描述：

洪尼玛有一家金融公司。有一天，有名黑客袭击了他公司的账户，第名黑客每分钟可以从账户中盗取元，对付第名黑客洪尼玛需要分钟进行防守、分钟进行攻击（该过程不会也不许被中断）。一旦洪尼玛对第名黑客开始进行攻防，该黑客将无法继续盗取钱财，但其他未被攻防的黑客可以继续盗取钱财。这名黑客从第0时刻开始进行袭击。洪尼玛想知道对付完这名黑客后被盗取的金额最小是多少？

输入格式：

第一行为一个正整数，表示黑客的数量；

接下来行，每行两个正整数、，表示第名黑客每分钟可以盗取的金额和洪尼玛对他进行攻防所需的时间；

对于60%的数据，；

对于100%的数据，、。

输出格式：

输出一个正整数，表示被盗取的最小金额。

样例输入：

5
1 1
2 2
3 3
4 4
5 5

样例输出：

170

解法：

一看这题目，典型的贪心算法啊，出处应该是某个牛吃草问题，要把牛一只一只送回去，路上花费来回两次的时间，看最终损失了多少草。

#include <iostream>
#include <cstdio>
#include <algorithm>
#define ll long long
#define Maxn 100000
using namespace std;
int n;
struct node
{
    int t;//攻防所需的时间
    int c;//每次偷的钱
};
node a[Maxn];
bool cmp(node x, node y)
{
    //    算一下哪个最能偷。。。
    double t1 = (x.c * 1.0) / (x.t * 1.0);
    double t2 = (y.c * 1.0) / (y.t * 1.0);
    return t1 > t2;
}
int main()
{
    scanf("%d", &n);
    ll sum = 0;
    ll ans = 0;
    for (int i = 0; i < n; i++)
    {
        scanf("%d%d", &a[i].c, &a[i].t);
        sum += a[i].c;
    }
    sort(a, a + n, cmp);

    for (int i = 0; i < n - 1; i++)
    {
        sum -= a[i].c;
        ans += sum * a[i].t * 2;
    }
    cout << ans << endl;
    return 0;
}

话不多说，代码骑脸上了还能不过？

注意一个问题，最好不要用int型去定义sum和ans，不用long或者long long的话，数据累计起来会当场去世。