自动搬运

查看原文

来自洛谷，原作者为

	operator_ I I I

搬运于2025-08-24 22:07:29，当前版本为作者最后更新于2023-10-09 09:48:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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;
}