结论：任何长度为 n n n的数组逆序对数最多为 n ( n − 1 ) 2 \dfrac{n(n-1)}{2} 2n(n−1)。
因为： ∑ i = 1 n − 1 i = n ( n − 1 ) 2 \sum_{i=1}^{n-1} i=\dfrac{n(n-1)}{2} ∑i=1n−1i=2n(n−1)
冒泡排序的原理就是根据减少逆序对实现的。 即相邻元素交换的次数等于逆序对数。
当且仅当数组为递减序( n n n个元素都不相同) 逆序对数= n ( n − 1 ) 2 \dfrac{n(n-1)}{2} 2n(n−1)成立。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=5e4+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7; #define mst(a,b) memset(a,b,sizeof a) #define lx x<<1 #define rx x<<1|1 #define reg register #define PII pair<int,int> #define fi first #define se second #define pb push_back #define il inline int t,n,a[N]; int main(){ scanf("%d",&t); while(t--){ scanf("%d",&n); int ok=0; for(int i=1;i<=n;i++){ scanf("%d",&a[i]); if(i>1&&a[i]>=a[i-1]) ok=1; } puts(ok?"YES":"NO"); } return 0; }