自动搬运

查看原文

来自洛谷，原作者为

	xiaoliebao1115 real life

搬运于2025-08-24 23:02:09，当前版本为作者最后更新于2024-08-17 12:08:32，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

小清新简单题。

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)$。