CF1077div2C

CF 1077 (div2) C. Restricted Sorting

Problem - C - Codeforces

题目概括为把一个序列变成不下降序列所花费的最小代价最大

明显可以二分答案
check：很显然的一个结论，对于两个点a，b借助最大值或者最小值一定是最优的，如果都不能就不合法

代码

#include <bits/stdc++.h>
using namespace std;
const int N=3e5+10;
int n;
int a[N],b[N],maxn,minn;
int check(int k){for(int i=1;i<=n;i++){if(a[i]!=b[i]){int c=abs(a[i]-minn)>=k;int d=abs(a[i]-maxn)>=k;if(!c&&!d){return 0;}}}return 1;
}
void solve(){cin>>n;for(int i=1;i<=n;i++){cin>>b[i];a[i]=b[i];}sort(b+1,b+n+1);maxn=b[n];minn=b[1];int f=0;for(int i=1;i<=n;i++){if(a[i]!=b[i]){f=1;break;}}if(!f){cout<<-1<<endl;return;}int l=0,r=maxn,ans;while(l<=r){int mid=(l+r)>>1;if(check(mid)){l=mid+1;ans=mid;}else{r=mid-1;}}cout<<ans<<endl;
}
int main(){int t;cin>>t;while(t--){solve();}return 0;
}