CF1637A题解
Sorting Parts
题面翻译
给定一个长度为 n 的数组 a。你可以执行恰好一次操作。每次操作选择一个在 [1,n-1] 内的整数 len，然后将数组 a 中长度为 len 的前缀和长度为 n-len 的后缀分别排序。请判断是否能够通过操作，使得最终的数组 a 不满足 \forall i\in[1,n)，a_i<= a（i+1）。
数据范围：
- t 组数据，1<= t<= 100。
- 2<= n,\sum n<= 10^4。
- 1<= a_i<= 10^9。
Translated by Eason_AC
题目描述
You have an array a of length n . You can exactly once select an integer len between 1 and n - 1 inclusively, and then sort in non-decreasing order the prefix of the array of length len and the suffix of the array of length n - len independently.
For example, if the array is a = [3, 1, 4, 5, 2] , and you choose len = 2 , then after that the array will be equal to [1, 3, 2, 4, 5] .
Could it be that after performing this operation, the array will not be sorted in non-decreasing order?
输入格式
There are several test cases in the input data. The first line contains a single integer t ( 1 <= t <= 100 ) — the number of test cases. This is followed by the test cases description.
The first line of each test case contains one integer n ( 2 <= n <= 10^4 ) — the length of the array.
The second line of the test case contains a sequence of integers a_1, a_2, ... , a_n ( 1 <= a_i <= 10^9 ) — the array elements.
It is guaranteed that the sum of n over all test cases does not exceed 10^4 .
输出格式
For each test case of input data, output "YES" (without quotes), if the array may be not sorted in non-decreasing order, output "NO" (without quotes) otherwise. You can output each letter in any case (uppercase or lowercase).
样例
样例输入
3
3
2 2 1
4
3 1 2 1
5
1 2 2 4 4
样例输出
YES
YES
NO
解题思路
由题可知这个操作就相当于把数组分为两半分别进行排序。通过样例不难看出，只要这一整个数组是非降序排列相当于升序，不过会有某些数相等的情况所以这么说，那么它分成两半再排序的结果与原来的数组是一样的。如果数组中有降序，就比如[1，3，2，4]其中的[3，2]就是降序，这时我们只要在[3，2]之间把数组分为两半进行排序它的结果就不是非降序排列的。
AC代码
#include<iostream>
#include<cstdio>
const int N = 1e4 + 10;
int q[N];
int main()
{
int t, n;
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
//要记住把falg的定义放在while循环里面。我就是忘了放，纠结了半天。qaq
bool flag = 1;
for (int i = 0; i < n; i++) {
scanf("%d", &q[i]);
if (q[i] < q[i - 1] && i > 0) {
flag = 0;
}
}
if (flag)
printf("NO\n");
else
printf("YES\n");
}
return 0;
}