考虑任意一个运送顺序,对于第 $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#include #include #include #include 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