今日份的题目。（指9月24日，因为比赛从晚上10点半持续到12点半）
问题A是水题，题面如下（大半夜了，就不翻译了，赶着睡觉）（其他题目明天再发）
Wheatley decided to try to make a test chamber. He made a nice test chamber, but there was only one detail absent — cubes.
For completing the chamber Wheatley needs n
cubes. i-th cube has a volume ai
.
Wheatley has to place cubes in such a way that they would be sorted in a non-decreasing order by their volume. Formally, for each i>1
, ai−1≤ai
must hold.
To achieve his goal, Wheatley can exchange two neighbouring cubes. It means that for any i>1
you can exchange cubes on positions i−1 and i
.
But there is a problem: Wheatley is very impatient. If Wheatley needs more than n⋅(n−1)2−1
exchange operations, he won’t do this boring work.
Wheatly wants to know: can cubes be sorted under this conditions?
Input
Each test contains multiple test cases.
The first line contains one positive integer t
(1≤t≤1000
), denoting the number of test cases. Description of the test cases follows.
The first line of each test case contains one positive integer n
(2≤n≤5⋅104
) — number of cubes.
The second line contains n
positive integers ai (1≤ai≤109
) — volumes of cubes.
It is guaranteed that the sum of n
over all test cases does not exceed 105
.
Output
For each test case, print a word in a single line: “YES” (without quotation marks) if the cubes can be sorted and “NO” (without quotation marks) otherwise.
Example
Input
3
5
5 3 2 1 4
6
2 2 2 2 2 2
2
2 1
Output
YES
YES
NO
实际上就是求逆序对。
主要运用的数学定理是，任意一个排列经过和逆序对数等同次数的相邻元素交换，可以得到有序的排列。
所以就是求逆序对的数量，再和n(n-1)/2-1做比较即可。
同时注意一下取值范围。
代码如下：
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 500005
using namespace std;
int T;
int n;
long long aim;
int num[maxn];
int r_num[maxn],l_num[maxn];
long long merge(int l,int r){
if(l==r){
return 0;
}
int mid=(l+r)>>1;
long long ans=0;
ans=merge(l,mid)+merge(mid+1,r);
int lind=0,rind=0;
for(int i=l;i<=mid;i++){
l_num[i-l]=num[i];
}
for(int i=mid+1;i<=r;i++){
r_num[i-mid-1]=num[i];
}
for(int i=l;i<=r;i++){
if(lind>(mid-l)){
num[i]=r_num[rind++];
}else if(rind>(r-mid-1)){
num[i]=l_num[lind++];
ans+=rind;
}else if(l_num[lind]<=r_num[rind]){
num[i]=l_num[lind++];
ans+=rind;
}else{
num[i]=r_num[rind++];
}
}
return ans;
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d",&n);
aim=1LL*n*(n-1)/2-1;
for(int i=0;i<n;i++){
scanf("%d",&num[i]);
}
long long step=merge(0,n-1);
// printf("%d ",step);
if(step<=aim){
printf("YES\n");
}else{
printf("NO\n");
}
}
return 0;
}