P5133 题解

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