本文主要是介绍题目：排序疑惑，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
问题描述：
解题思路：
做的时候没想到，其实这是以贪心题。我们可以每次排最大的区间（小于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;
}知识点：贪心
这篇关于题目：排序疑惑的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
