题解：P10885 【MX-S3-T1】「FeOI Round 1」野心

xyx4042024-08-182024-10-19

思路：

题目中给出的是一个排列 $p$ 。
排列说明了这个数组是由一到 $n$ 组成的，且不重复。

那么对于这个排列我们可以从一到 $n-1$ 依次枚举，对于每次访问到的第 $i$ 个数，记录最大值和最小值，相减判断是否是等差数列。

当 $i \gt 2$ 时，对于一到 $i$ ，排完序的数组等差数列只能是一或二。
但是这么做只能判断等差为一的情况，所以还要特判一下。

由于 $i$ 要大于二，而 $i$ 最大为 $n-1$ 所以我们要特判一下 $n \le 3$ 的情况。

代码：

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define itn int
#define ull unsigned long long
LL a[1000005];
void slove(){
	LL mx=INT_MIN,mn=INT_MAX,n,ans=0;
	bool flag1=1,flag2=1;
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		if(a[i]%2==1&&i<=n/2)flag2=0;
		if(a[i]%2==0&&i<=(n+1)/2)flag1=0;
	}
	if(n==1){// 特判 n<=3
		printf("0\n");
		return;
	}
	else if(n==2){
		printf("1\n");
		return;
	}
	else if(n==3){
		printf("2\n");
		return;
	}
	if(flag2||flag1)ans++;
	for(int i=1;i<=n-1;i++){
		mx=max(mx,a[i]);mn=min(mn,a[i]);// 记录最大值和最小值 
		if(i==2&&mx==n&&mn==1){// 前两个数字为 1 和 n
			ans++;
			continue;
		}
		if(mx-mn+1==i&&(mx==n||mn==1))ans++;
	}
	if((a[n]==1||a[n]==n)&&(a[n-1]==1||a[n-1]==n))ans++;
	printf("%lld\n",ans);
	return;
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		slove();
	}
	return 0;
}