题面

点击此处前往原题。

约翰留下他的$n\in [1,10^5]\bigcap\mathbb{N^*}$只奶牛上山采木。他离开的时候，她们像往常一样悠闲地在草场里吃草。可是，当他回来的时候，他看到了一幕惨剧：牛们正躲在他的花园里，啃食着他心爱的美丽花朵！为了使接下来花朵的损失最小，约翰赶紧采取行动，把牛们送回牛棚。

牛们从$1$到$n$编号。第$i$只牛所在的位置距离牛棚$t_i\in [1,2\times 10^6]\bigcap\mathbb{N^*}$分钟的路程，而在约翰开始送她回牛棚之前，她每分钟会啃食$d_i\in [1,10^2]\bigcap\mathbb{N^*}$朵鲜花。无论多么努力，约翰一次只能送一只牛回棚。而运送第$i$只牛事实上需要$2t_i$分钟，因为来回都需要时间。试求最小的被吞食的花朵数量。

题解

考虑贪心。本题目类似于国王游戏。按照$\cfrac{t}{d}$的值从小到大贪心。考虑到误差，需要移项。

代码

#include <bits/stdc++.h>
using namespace std;
struct Cow {
    unsigned long long t;
    unsigned long long d;
    bool operator<( const Cow& that ) const {
        return t * that.d < that.t * d;
    }
} c[100005];
int main() {
    ios::sync_with_stdio( false );
    cin.tie( 0 );
    unsigned long long n, ans = 0, nowt = 0;
    cin >> n;
    for ( unsigned long long i = 1; i <= n; i++ ) {
        cin >> c[i].t >> c[i].d;
    }
    sort( c + 1, c + 1 + n );
    for ( unsigned long long i = 1; i <= n; i++ ) {
        ans += nowt * c[i].d;
        nowt += c[i].t << 1;
    }
    cout << ans << endl;
    return 0;
}

版权声明：本文是原创文章，版权归 星雾月雨 所有。

本文链接：https://www.ariels.xyz/archives/860.html

本站所有下方标记为「允许规范转载」的原创文章均采用 署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可。
您可以自由地转载，但请务必注明文章来源且不可用于商业目的。