题意:
n头牛,每次搬运一头牛回到起始点,搬运每头牛的时间为Ti,从起点返回回来也需要Ti的时间,没搬运的牛每分钟会破坏di朵花,问最少会破坏多少朵花。
容易知道,对于任意两头相邻的牛,搬运的顺序不会影响其他牛造成的破坏,那么我们计算先搬运A在搬运B破坏值就是
先搬运b在搬运a破坏值为
假设前者更优秀则有
化简后得到
所以按照上述式子,对牛进行排序,按顺序搬运牛即可,维护一个变量表示在搬运这头牛之前花了多少时间,即在搬运他之前他破坏了多少分钟。
#include<bits/stdc++.h> using namespace std; #define int long long struct node{int t,d;} a[1<<17]; signed main(){ int n;cin>>n; for(int i=1;i<=n;i++){ cin>>a[i].t>>a[i].d; } sort(a+1,a+1+n,[](node a,node b){ return a.t*b.d<b.t*a.d; }); int ans=0,Time=0; for(int i=1;i<=n;i++){ ans+=Time*a[i].d; Time+=2*a[i].t; } cout<<ans; return 0; }