考虑任意一个运送顺序，对于第 $i$ 头牛和第 $j=i+1$ 头牛，把它们的顺序交换会如何
首先其他牛的代价仍然不变
改变的代价为 $2t[i]*v[j]-2t[j]*v[i]$，如果左边式子小于 $0$，我们就把这两头牛交换，一直交换最终代价就是最小的
所以直接按 $t[i]/v[i]$ 排序就好了，$cmp$ 函数可以写成 $t[i]*v[j]<t[j]*v[i]$
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<‘0‘||ch>‘9‘) { if(ch==‘-‘) f=-1; ch=getchar(); } while(ch>=‘0‘&&ch<=‘9‘) { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=2e5+7; int n; struct dat{ int x,y; inline bool operator < (const dat &tmp) const { return x*tmp.y<y*tmp.x; } }d[N]; int main() { n=read(); for(int i=1;i<=n;i++) d[i].x=read(),d[i].y=read(); sort(d+1,d+n+1); ll now=0,ans=0; for(int i=1;i<=n;i++) { ans+=now*d[i].y; now+=2*d[i].x; } printf("%lld\n",ans); }
BZOJ 1634. [Usaco2007 Jan]Protecting the Flowers 护花
原文：https://www.cnblogs.com/LLTYYC/p/11367940.html