题面

点击此处前往原题

约翰留下他的$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;
}
Last modification:October 23rd, 2020 at 07:07 pm
如果您觉得我的文章有用,给颗糖糖吧~