题目：排序疑惑

问题描述：

解题思路：

        做的时候没想到，其实这是以贪心题。我们可以每次排最大的区间（小于n，即n-1大的区间），再判断是否有序 。因此只需要分别判断排（1~n-1）和（2~n）这两个区间时整个数组是否能非降序。

        注意点：1.非降序是指等于和升序两种情况。

                       2.每次判断要注意恢复原来数组，避免继承（AC代码一）

AC代码：

        1：手动判断

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 9;
int a[N];
int b[N];

void slove(){
	int n;cin >> n;
	for(int i = 1; i <= n; i++)cin >> a[i];
	for(int i = 1; i <= n; i++)b[i] = a[i];  // 复制一份原数组
 	if (n == 1)
 	{
 		cout << "YES" << '\n';
 		return ;
	}
		
	int k = 2;
	while(k > 0)
	{
		for(int i = 1; i <= n; i++)b[i] = a[i];  // 恢复原数组状态
		
		sort(b + k, b + k + n - 1);
			
		for(int i = 1; i < n; i++)
		{
			if(b[i] > b[i + 1])break;
			if(i == (n-1)){
				cout << "YES" << '\n';
				return ;	
			} 
		}
		
		k--;
	}	
	cout << "NO" << '\n';
	return ;
}


int main()
{
	int t;cin >> t;
	
	while(t--)
	{
		slove();
	}
	return 0;
}

        2：利用*max_element,*min_element

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6;
int a[N];

void slove()
{
	int n;cin >> n;
	for(int i = 1; i <= n; i++)cin >> a[i];
	
	for(int i = 1; i <= 2; i++)
	{
		if(i == 1 && a[n] >= *max_element(a + 1, a + n))  // 等价于给1~n-1排序,这段区间的最大值小于等于a[n]就表明其为非降序
		{
			cout << "YES" << '\n'; 
			return ;
		} 
		if(i == 2 && a[1] <= *min_element(a + 2, a + n + 1))  // 同理
		{
			cout << "YES" << '\n';
			return ;
		}
	}
	
	cout << "NO" << "\n";
}
int main()
{
	int t;cin >> t;
	while(t--)
	{
		slove();
	}
	return 0;
}

知识点：贪心