算法1 贪心
如上图
那么其实我们要的是最大值
容易知道上面的K是定值 下面的K1也是定值
所以对答案有影响的在于相邻的a和b两头牛谁在上面
那么根据图中列出的式子
我们算出a在前(上) 两头牛风险的最大值
算出b在前(上)两头牛风险的最大值
然后取最小即可。
C++ 代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e4+50;
struct node{
ll w,s;
}a[N];
int main(){
int n;cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].w>>a[i].s;
}
sort(a+1,a+n+1,[](node a,node b){
ll x1=-a.s,y1=a.w-b.s;
ll x2=-b.s,y2=b.w-a.s;
if(x1<y1) x1=y1;
if(x2<y2) x2=y2;
return x1<x2;
});
ll W=0,ma=-1e18;
for(int i=1;i<=n;i++){
ma=max(ma,W-a[i].s);
W+=a[i].w;
}
cout<<ma;
return 0;
}