Protecting the Flower【每日一题】5月28日

一.题目链接

$\quad$ Protecting the Flower

二.题目大意

$\quad$ 有 n 头牛，每头牛有两个属性 t[i] 和 d[i]，代表从原点走到第 i 头牛所花的时间，d[i] 代表第 i 头牛每单位时间吃花的个数，当牛被选中后，牛便不再吃花.你的初始位置在原点，每次只能牵一头牛，求把所有牛牵到原点后，所有牛吃花总和的最小值.

三.分析

$\quad$ 贪心临项交换的经典题目.

$\quad$ 假设最优的选择顺序为 ...AB...，那么交换 AB 的顺序这一操作不会对其他牛产生任何影响.

$\quad$ 由于我们已经假设最优选择顺序为 ...AB...，所以 ...BA... 的结果不应该比之前的好.

$\quad$ 即 AB 应该不比 BA 差.

$\quad$ AB 的吃花数量为 2 * t[A] * d[B]；BA 的吃花数量为 2 * t[B] * d[A].

$\quad$ 所以 2 * t[A] * d[B] <= 2 * t[B] * d[A].

$\quad$ 即 t[B] * d[A] <= t[B] * d[A].

$\quad$ 所以我们只需按照上式排序，得到的序列便是最优安排方案.

$\quad$ 排序方法如下

bool cmp(node a, node b)
{
    return a.t * b.d < b.t * a.d;
}

$\quad$ 得到最优安排方案后，剩下的只需模拟牵牛与吃花的过程就好啦.

$\quad$ 完整代码如下

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int M = (int)1e5;
const ll mod = (ll)1e9 + 7;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;

struct node
{
    int t, d;
}s[M + 5];

bool cmp(node a, node b)
{
    return a.t * b.d < b.t * a.d;
}

int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    int n; scanf("%d", &n);
    for(int i = 1; i <= n; ++i) scanf("%d %d", &s[i].t, &s[i].d);
    sort(s + 1, s + n + 1, cmp);
    ll ans = 0, t = 0;
    for(int i = 1; i <= n; ++i)
    {
        ans += t * s[i].d;
        t += 2 * s[i].t;
    }
    printf("%lld\n", ans);
    return 0;
}