problem
有n头牛在吃花,第i头牛每分钟吃的花,John每次可以运走一头牛,运走第i头牛需要的时间是。设计一种运牛的顺序,使得被吃掉的花最少。
solution
非常经典贪心题。
先考虑只有两头牛的情况。如果先运走,那么被吃掉的花就是,同理如果先运走被吃掉的花就是。所以我们按照排序,然后统计答案就行了。
code
/* * @Author: wxyww * @Date: 2020-05-27 22:08:27 * @Last Modified time: 2020-05-27 22:09:59 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cstring> #include<algorithm> #include<queue> #include<vector> #include<ctime> #include<cmath> using namespace std; typedef long long ll; const int N = 100010; ll read() { ll x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); } return x * f; } struct node { int t,d; }a[N]; bool cmp(const node &A,const node &B) { return A.t * B.d < B.t * A.d; } int main() { int n = read(); for(int i = 1;i <= n;++i) a[i].t = read(),a[i].d = read(); sort(a + 1,a + n + 1,cmp); int now = 0; ll ans = 0; for(int i = 1;i <= n;++i) { ans += now * a[i].d; now += a[i].t + a[i].t; } cout<<ans<<endl; return 0; }