题目
原题链接:https://codeforc.es/problemset/problem/1420/A
思路
题目大意：给定n个数，要求将其排列成为一个非降序的新数组，即a[i]<=a[i+1]，每次操作可以交换两个相邻的数的位置，最多可以交换n*（n-1）/2 -1次，问可以达到目的吗。
交换次数即为逆序数之和
而我们观察其给定的最大操作数 n*（n-1）/2 -1正好比完全逆序需要的操作少一个，所以实际上题目只有在完全逆序的时候才会无法通过，因此只要判断n个数中有没有正序数对存在即可。
逆序数->高数内容，可以百度一下。
代码实现
#include <iostream>
#include <cstring>
using namespace std
;
const int MAX
= 5e4 + 5;
int t
;
int n
, a
[MAX
];
int main() {
ios
::sync_with_stdio(false);
cin
.tie(0);
cout
.tie(0);
cin
>> t
;
while (t
--)
{
memset(a
, 0, sizeof(a
));
cin
>> n
;
for (int i
= 1; i
<= n
; i
++)
cin
>> a
[i
];
int f
= 0;
for (int i
= n
; i
>= 2; i
--)
if (a
[i
] >= a
[i
- 1]) {
f
= 1; break;
}
cout
<< (f
== 1 ? "YES" : "NO") << endl
;
}
return 0;
}
