自动搬运

查看原文

来自洛谷，原作者为

	sbno333 不进北省不改签！！！

搬运于2025-08-24 22:14:55，当前版本为作者最后更新于2023-07-23 15:36:16，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

其实这道题比较水，果然是远古时期的题我们假设每一名同学都向一个方向移动，此时距离确定，我们发现，如果考虑两个方向，比如有 $6$ 名同学，一个座位到任意座位最近距离有可能有以下情况：

为 $n=7$ 时:

而当我们指定方向时，就有距离为 $0$ 到 $n-1$ 中的一种，我们发现 $\lfloor \frac{n}{2} \rfloor$ 是临界点，如果值大于它，实际距离就会减小。

当 $n=6$ 时：

当 $n=7$ 时：

不难发现我们可以将座位号进行转圈,比如 $1,2,3 \rightarrow 2,3,1$。

此时特定距离将同时加或减一个数，超界就循环，比如 $-1\rightarrow n-1$，$n\rightarrow 0$。

但不管怎样，都是离 $\lfloor \frac{n}{2} \rfloor,\lceil \frac{n}{2} \rceil$ 越远越好。

然而，对应 $\lfloor \frac{n}{2} \rfloor$，$\lceil \frac{n}{2} \rceil$ 的特定方向距离，于是我们就用没有对应特定方向距离的同学来对应，而周围的座位也对应，因此我们要求所有特定距离中最长连续的没有同学满足的长度。

由于转座位时，距离会循环，因此我们要特判两边的连续无同学对应的和。

我们再分成偶数和奇数两种情况，进行判断距离。

当然这样你以为就对了么？

不！你会获得 $66$ 分的好成绩作者我第一次提交的成绩，调试了好几遍，因为题目中有这句话：

需要注意的是 $p_1$ 可以坐在 $p_n$ 左边也可以坐在 $p_n$ 右边。

因此我们要把 $p$ 数组倒过来算一遍，输出最小值。

$CODE$

#include<bits/stdc++.h>
using namespace std;
bool t[1000009];
int a[1000009];
int main(){
	int n;
	int ma;
	int u;
	int x,y;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	
	memset(t,0,sizeof(t));
	for(int i=1;i<=n;i++){//特定方向距离记录
		t[(a[i]-i+n)%n]=1;
	}
	ma=0;
	u=0;
	for(int i=0;i<n;i++){//算最长连续无同学对应座位
		if(t[i]){
			ma=max(ma,u);
			u=0;
		}else{
			u++;
		}
	}
	ma=max(ma,u);
	u=0;
	for(int i=0;i<n;i++){//特判循环
		if(!t[i]){
			u++;
		}else{
			break;
		}
	}
	for(int i=n-1;i>=0;i--){
		if(!t[i]){
			u++;
		}else{
			break;
		}
	}
	ma=max(ma,u);
	
	x=n/2;
	if(n%2){//分奇偶情况
		x-=ma/2;
	}else{
		if(ma>0){
			x--;
			ma--;
		}
		x-=ma/2;
	}
	memset(t,0,sizeof(t));//倒过来算
	for(int i=1;i<=n;i++){
		t[(a[n+1-i]-i+n)%n]=1;
	}
	ma=0;
	
	u=0;
	for(int i=0;i<n;i++){
		if(t[i]){
			ma=max(ma,u);
			u=0;
		}else{
			u++;
		}
	}
	ma=max(ma,u);
	u=0;
	for(int i=0;i<n;i++){
		if(!t[i]){
			u++;
		}else{
			break;
		}
	}
	for(int i=n-1;i>=0;i--){
		if(!t[i]){
			u++;
		}else{
			break;
		}
	}
	ma=max(ma,u);
	
	y=n/2;
	if(n%2){
		y-=ma/2;
	}else{
		if(ma>0){
			y--;
			ma--;
		}
		y-=ma/2;
	}
	cout<<min(x,y);
	return 0;
}

不难发现这是贪心作者我写到几乎末尾才发现 思路的话我思路不是特别清晰，所以写的特别啰嗦，所以大家主要看代码，思路仅供参考，帮助大家理解，祝大家切题愉快。