ARC100 D - Equal Cut
Description: 给出长度为n的序列A，把这个序列分成连续的四段，最小化极差。
\(4≤n≤2×10^5,4≤n≤2×10^5\)
Solution:枚举中间的分割点，左右二分出极差最小的位置更新答案。
code:
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
using namespace std;
const int MAXX=200010;
long long a[MAXX];
long long sum[MAXX];
int n;
long long ans=0x3f3f3f3f;
long long minnn1=0x3f3f3f3f;
long long maxxx1=0;
long long minnn2=0x3f3f3f3f;
long long maxxx2=0;
inline void solve(int L,int R,int v){
int l=L;
int r=R;
if(l>r)return ;
while(l+1<r){
int mid=(l+r)>>1;
if(sum[mid]-sum[L-1]>(sum[R]-sum[mid]))r=mid;
else l=mid;
}
if(v==1){
if(abs(sum[l]-sum[L-1]-(sum[R]-sum[l]))<abs(sum[r]-sum[L-1]-(sum[R]-sum[r]))){
minnn1=min(sum[l]-sum[L-1],sum[R]-sum[l]);
maxxx1=max(sum[l]-sum[L-1],sum[R]-sum[l]);
}
else {
minnn1=min(sum[r]-sum[L-1],sum[R]-sum[r]);
maxxx1=max(sum[r]-sum[L-1],sum[R]-sum[r]);
}
}
else {
if(abs(sum[l]-sum[L-1]-(sum[R]-sum[l]))<abs(sum[r]-sum[L-1]-(sum[R]-sum[r]))){
minnn2=min(sum[l]-sum[L-1],sum[R]-sum[l]);
maxxx2=max(sum[l]-sum[L-1],sum[R]-sum[l]);
}
else {
minnn2=min(sum[r]-sum[L-1],sum[R]-sum[r]);
maxxx2=max(sum[r]-sum[L-1],sum[R]-sum[r]);
}
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
cin>>a[i];
sum[i]=sum[i-1]+a[i];
}
for(int i=1;i<=n;++i){
if(i<2||n-i<2)continue;
minnn1=0x3f3f3f3f;
maxxx1=0;
minnn2=0x3f3f3f3f;
maxxx2=0;
solve(1,i,1);
solve(i+1,n,0);
ans=min(max(maxxx1,max(maxxx2,max(minnn1,minnn2)))-min(maxxx2,(min(maxxx1,min(minnn1,minnn2)))),ans);
}
cout<<ans;
return 0;
}