P4409 [ZJOI2006]皇帝的烦恼

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int const N=1e5+7;
int n;
int a[N];
int fn[N]; //在不与集合i-1冲突（重复）下，与集合1最小的重复数 
int fx[N]; //在不与i-1冲突下，与1最大的重复数 
bool pan(int x){
	fn[1]=a[1];fx[1]=a[1];  //
	for(int i=2;i<=n;++i){
		fx[i]=min(a[i],a[1]-fn[i-1]);
		fn[i]=max(0,a[i]-(x-(a[1]+a[i-1]-fx[i-1])));
	}
	if(fn[n]==0) return 1;
	else return 0;
}
int main(){
	cin >> n;
	int l=0;
	for(int i=1;i<=n;++i){
		cin >> a[i];
		l=max(l,a[i]+a[i-1]);
	}
	int r=300000;
	while(l<=r){
		int mid=(l+r) >> 1;
		if(pan(mid)) r=mid-1;
		else l=mid+1;
	}
	cout << l ;
	return 0;
}