CodeForces1420A

题意

给出(T)组数据，每组数据给出一个(n)和一个长度为(n)的数列，

我们可以对相邻元素进行交换，要求我们在 (frac{n cdot(n-1)}{2}-1) 的次数内把该数列排序，

排序的结果要求是 非递减 （注意：递减也不行），

如果可以排出来，则输出 YES ，否则输出 NO 。

思路

这题是A题，所以看到题目第一反应还是sort排序，给出的公式 (frac{n cdot(n-1)}{2}-1) 又感觉像冒泡排序的时间复杂度，但是肯定和冒泡没啥关系啦，毕竟

冒泡时间复杂度是 (n^2) ，而且感觉又是A题代码应该不会太长（确实不长但是我可能想到），而且数据也不是很大，

但是之后还是总觉得哪里有点问题，最终，还真的不是我想的思路。

正确的思路

首先我们计算一下如果是一个完全递减的数列，那么把它有序我们最多需要 ((n−1)+(n−2)+ ⋅ ⋅ ⋅ +1) 次的移动，

对该公式我们用等比数列求一下和，就是 (n imes(n-1){div}2) 次，

我们会突然发现题目要求的是最多 (frac{n cdot(n-1)}{2}-1) 的次数，但是 (n imes(n-1){div}2) 正好比规定的要多(1)，所以我们不可能去移动所有的
元素，（也间接的说明了，如果一个数组是 完全递减 的，那么就直接输出 NO ，否则输出 YES 。

所以这种是必不可能的，那么对于其他不是完全递减的数组自然是可以完成的（至少会比完全递减数组操作数少1，自然满足）。故我们只要判断是不是完全递减的数组即可

补充一个看起来有关系但是和本题没关系的公式：
全排列数 (f(n)=n!) (定义 (0!=1) )。

AC代码

#include<iostream>
#include<string.h>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include<list>
#include<stdlib.h>
#include<map>
#include<stack>
#include<stdio.h>
#include<queue>
using namespace std;
typedef long long ll;
#define sc(T) scanf("%d",&T)
#define scc(x,y) scanf("%d %d",&x,&y)
#define pr(T) printf("%d
",T)
#define f(a,b,c) for (int a=b;a<c;a++)
#define ff(a,b,c) for (int a=b;a>c;a--)
#define inf 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
#define eps 1e-9
#define PI acos(-1)

int a[50010];

int main()
{
    int T;
    sc(T);
    while(T--)
    {
        int n,flag=0;
        sc(n);
        f(i,0,n)
        {
            sc(a[i]);
            if(i!=0&&a[i-1]<=a[i])
                flag=1;
        }
        if(flag)
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
//        f(i,0,n)
//        {
//            sc(a[i]);
//            if(i!=1&&a[i]!=a[i-1])
//                flag=1;
//        }
//        if(!flag)
//        {
//            cout<<-1<<endl;
//            continue;
//        }
//        int cnt=n*(n-1)/2-1;
    }
    return 0;
}