P5133 tb148的客人

题目传送门

题解

唯一的一篇题解还是交错题的……

很简单的一个二分加差分题。

显然是二分答案，考虑检验。如果 \(2mid+1\ge n\)，那么所有人可以自由去到任意位置，一定可行；否则，我们求出每个人可以去到的区间范围，并以此推出要满足这个人的限制，\(1\) 号需要在哪个区间内（这里我们只考虑顺时针 \(1-n\) 的情况，逆时针的话，把原数组翻转就可以了），\(mid\) 可行就等价于这些区间有交。我们可以把每个区间 \(+1\)，最后检验是否有点被加了 \(n\) 次，这是简单的差分可以做到的。不过要注意，这题是在环上的，所以我们要判断一下区间的 \(l\) 是否大于 \(r\)，若是，我们把原区间拆成 \([1,r]\) 和 \([l,n]\) 这两个，显然这两个区间不会有交，所以正确性得证。

事实上，还有一种用 set 的做法，大致就是递推出每一种结局的最优方案，但是代码实现起来细节会很多，此处略。

代码：

#include<bits/stdc++.h>
using namespace std;
inline int read() {
	int s=0,m=0;char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-')m=1;ch=getchar();}
	while( isdigit(ch)) s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
	return m?-s:s;
}
int n,a[1000005],b[1000005];
bool check(int mid) {
	if(mid*2+1>=n) return 1;
	for(int i=1;i<=n+1;i++) b[i]=0;
	for(int i=1;i<=n;i++) {
		int l=(i-mid-a[i]+1+n*2-1)%n+1,r=(i+mid-a[i]+1+n*2-1)%n+1;
		if(l<=r) b[l]++,b[r+1]--;
		else b[1]++,b[r+1]--,b[l]++,b[n+1]--;
	}
	for(int i=1,s=0;i<=n;i++)
		if((s+=b[i])==n) return 1;
	for(int i=1;i<=n+1;i++) b[i]=0;
	for(int i=1;i<=n;i++) {
		int l=(i-mid-a[n-i+1]+1+n*2-1)%n+1,r=(i+mid-a[n-i+1]+1+n*2-1)%n+1;
		if(l<=r) b[l]++,b[r+1]--;
		else b[1]++,b[r+1]--,b[l]++,b[n+1]--;
	}
	for(int i=1,s=0;i<=n;i++)
		if((s+=b[i])==n) return 1;
	return 0;
}
signed main() {
	cin>>n;
	for(int i=1;i<=n;i++)
		a[i]=read(); 
	int l=0,r=n,mid,ans;
	while(l<=r) {
		mid=(l+r)>>1;
		if(check(mid)) r=mid-1,ans=mid;
		else l=mid+1;
	}
	cout<<ans;
	return 0;
}