对称排序（蓝桥杯）

对称排序

问题描述

小蓝是一名软件工程师，他正在研究一种基于交换的排序算法，以提高排序的效率。

给定一个长度为 N 的数组 A，小蓝希望通过交换对称元素的方式对该数组进行排序。

具体来说，小蓝可以对数组 A 执行以下操作任意次数：

选择某个索引 (1≤i≤N ) 并交换从前往后数第 i 个元素和从后往前数第 i 个元素。

更正式地，选择一个索引 i 并交换 A_i和 A_N+1−i。

请帮助小蓝判断是否可以使用任意（可能为零）次操作将数组 A 变为有序。

输入格式
第一行包含一个整数 N，表示数组 A 的长度。

第二行包含 N 个整数 A₁ ,A₂ ,⋯,A_N ，以空格隔开。

数据范围保证：
1≤N≤10⁵,1≤A_i ≤10⁹ 。

输出格式
如果可以通过任意次操作对 A 进行排序，则输出 “YES”。否则，输出 “NO”。

样例输入

4
4 3 2 1

样例输出

YES

说明
对于样例，交换 (A₁ ,A₄) 和 (A₂ ,A₃ ) 后数组可以变为有序。

模拟

这段代码的目的是为了解决“对称排序”问题。该问题描述了一种特殊的排序算法，即通过交换数组中对称位置的元素来实现数组的排序。代码首先读入数组长度和数组元素，然后尝试通过对称交换操作来排序数组。最终判断是否能够通过这种操作使数组有序。下面是详细的代码注释说明：

#include<bits/stdc++.h> // 包含大多数标准库
using namespace std;   // 使用标准命名空间

int a[100010], b[100010]; // 定义两个数组a和b，用于存储输入的数组和排序后的数组
int n; // 定义数组长度n

int main()
{
	cin>>n; // 读取数组长度
	// 读取数组元素，并同时复制到数组b中
	for(int i=1; i<=n; i++)
	{
		cin>>a[i];
		b[i]=a[i];
	}
	
	// 对数组b进行排序，以便之后比较数组是否有序
	sort(b+1, b+1+n);
	
	// 首先检查数组a在没有任何交换的情况下是否已经有序
	for(int j=1; j<=n; j++)
	{
		if(a[j] != b[j]) // 如果发现数组a中的元素与数组b不同，则需要进行交换
		{
			break; // 退出循环，进行下一步的交换操作
		}
		if(j==n && a[j] == b[j]) // 如果到数组的最后一个元素都相同，说明数组已经有序
		{
			printf("YES"); // 输出YES
			return 0; // 程序结束
		}
	}
	
	// 如果数组a不是有序的，尝试通过交换对称元素的方式对数组进行排序
	for(int i=1; i<=n/2; i++) // 只需要遍历到数组的一半
	{
		if(a[i] > a[n+1-i]) // 如果前面的元素大于对称位置的元素，则交换它们
			swap(a[i], a[n+1-i]);
		// 每次交换后，都需要检查数组是否有序
		for(int j=1; j<=n; j++)
		{
			if(a[j] != b[j]) // 如果发现数组a中的元素与数组b不同，则需要继续交换
			{
				break; // 退出内层循环，继续外层循环的下一个交换
			}
			if(j == n && a[j] == b[j]) // 如果到数组的最后一个元素都相同，说明数组已经有序
			{
				printf("YES"); // 输出YES
				return 0; // 程序结束
			}
		}
	}
	
	printf("NO"); // 如果尝试了所有的交换操作后数组仍然无法有序，输出NO
	return 0; // 程序结束
}

程序首先读取数组并复制到另一个数组进行排序，以便比较。然后检查原数组是否已经有序。如果不是，代码会尝试通过对称交换操作使数组有序。在每次尝试交换后，都会检查数组是否已经有序。如果所有可能的交换操作都无法使数组有序，则输出"NO"。如果可以通过交换使数组有序，则输出"YES"。注意，数组的索引从1开始。