526互联

Atcoder Regular Contest 117 F - Gateau

发布时间 2023-07-14 11:47:57作者: tzc_wk

首先答案显然满足可二分性，于是不管三七二十一先上个二分。

不难发现题目中的限制形如：

  • \(s_{i+n-1}-s_{i-1}\ge X_i(i\le n)\)
  • \(s_{i-1}-s_{i-n-1}\le s_{2n}-X_i(i>n)\)

转换一下限制就变成 \(s_{i+n}-s_{i}\in[l_i,r_i](0\le i<n)\)。

再结合前缀和固有的性质，等价于 check 是否存在一个序列满足：

  • \(s_0=0,s_{2n}=mid\)
  • \(s_i\le s_{i+1}\)
  • \(s_{i+n}-s_{i}\in[l_i,r_i](0\le i<n)\)

先考虑朴素做法：我枚举 \(s_n\)，然后贪心地确定 \(s_1\sim s_{n-1}\) 以及 \(s_{n+1}\sim s_{2n-1}\)。确定方法是：假设我们已经知道 \(s_0\sim s_{i-1},s_n\sim s_{i+n-1}\)，那么如果 \(s_{i+n-1}-s_{i-1}\in[l_i,r_i]\)，那么就 \(s_{i+n-1}=s_{i+n},s_i=s_{i-1}\)，否则如果 \(s_{i+n-1}-s_{i-1}<l_i\) 就 \(s_{i}=s_{i-1},s_{i+n}=s_{i}+l_i\)，否则 \(s_{i+n}=s_{i+n-1},s_i=s_{i+n}-r_i\)。最后 check 是否有 \(s_{n-1}\le s_n\) 和 \(s_{2n-1}\le mid\)。

容易发现 \(s_{n-1}\) 和 \(s_{2n-1}\) 都随 \(s_n\) 的增大而增大，于是二分找到最大的 \(s_n\) 使得最终 \(s_{n-1}\le s_n\)，然后再 check 是否有 \(s_{2n-1}\le mid\)。

const int MAXN=3e5;
int n,a[MAXN+5],l[MAXN+5],r[MAXN+5];ll s[MAXN+5];
void calc(int mid){
	s[n]=mid;
	for(int i=1;i<n;i++){
		if(l[i]<=s[i+n-1]-s[i-1]&&s[i+n-1]-s[i-1]<=r[i])s[i]=s[i-1],s[i+n]=s[i+n-1];
		else if(s[i+n-1]-s[i-1]<l[i])s[i]=s[i-1],s[i+n]=s[i]+l[i];
		else s[i]=s[i+n-1]-r[i],s[i+n]=s[i+n-1];
	}
}
bool check(int x){
	for(int i=0;i<n;i++)l[i]=a[i+1],r[i]=x-a[i+n+1];
	for(int i=0;i<n;i++)if(l[i]>r[i])return 0;
	int L=l[0],R=r[0],p=-1;
	while(L<=R){
		int mid=L+R>>1;calc(mid);
		if(s[n]>=s[n-1])p=mid,R=mid-1;
		else L=mid+1;
	}
	if(p==-1)return 0;calc(p);
	return s[2*n-1]<=x;
}
int main(){
	scanf("%d",&n);for(int i=1;i<=n*2;i++)scanf("%d",&a[i]);
	int L=0,R=1.05e9,p=0;
	while(L<=R){
		int mid=L+R>>1;
		if(check(mid))p=mid,R=mid-1;
		else L=mid+1;
	}printf("%d\n",p);
	return 0;
}