题解：P10883 [COCI 2017-2018#2] Doktor

· · 题解

小清新简单题。

idea

注意到对于一个数来讲，他若能在反转后去到一个 a_i=i 的地方，那么旋转中心一定就是 (a_i+i)\div2。

所以说对于任意一个数，他能够反转到想去的位置的旋转中心有且仅有一个。

那么可以对于每一个旋转中心，记录所有能够以他为中心变到 a_i=i 的数的 \min(a_i,i)。因为实际上将 i 变到 a_i 的位置和将 a_i 变到 i 的位置，他俩是等价的。

那么枚举所有旋转中心，将他记录的所有数从大到小排序，枚举这里面的所有数作为旋转左端点，枚举到了第 x 个，也会使得第 1 到 x-1 这些数转到自己想到的位置。

所以用 x-sum_r+sum_{l-1} 和当前的答案作比较即可，sum 代表前缀和，表示 l 到 r 之中原来就 a_i=i 的数的个数。

code

int a[nn],n,sum[nn],ans,ans1,ans2;
vector<int> e[nn*2];
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
int main(){
    n=read();
    for(int i=1;i<=n;i++){
        a[i]=read(),sum[i]=sum[i-1];
        if(a[i]==i) sum[i]++;
        e[a[i]+i].push_back(min(a[i],i));
    }
    for(int i=2;i<=n*2;i++){
        sort(e[i].begin(),e[i].end(),greater<int>());
        for(int j=0;j<e[i].size();j++){
            int l=e[i][j];
            if(j+1-sum[i-l]+sum[l-1]>ans){
                ans=j+1-sum[i-l]+sum[l-1];
                ans1=a[l],ans2=a[i-l];
            }
        }
    }
    if(ans1==0&&ans2==0) cout<<1<<" "<<1<<endl;
    else cout<<ans1<<" "<<ans2<<endl;
    return 0;
}

注意对于你并未搜到任何答案的情况，说明没有必要进行反转操作，输出 1 即可，相当于没有操作。

时间复杂度 O(n\log n)。