Codeforce 1420 A. Cubes Sorting 解析(思維)

今天我們來看看CF1420
題目連結

題目
給一個數列$a$，求能不能在不超過$\frac{n(n-1)}{2}-1$次相鄰元素的調換下，得到遞增數列。

前言

b

想法

注意到，這是$A$題，所以一定不會要你構造太難的東西。
注意到$\frac{n(n-1)}{2}-1$很可疑，這一定代表某個東西。
觀察到我們至多至多，就是需要$\frac{n(n-1)}{2}$步來調換數列，因為如果目前數列數字是全部相異且是遞減，那麼慢慢把每個數字放到他應有的位置，需要$(n-1)+(n-2)+…+1=\frac{n(n-1)}{2}$步。
因此我們只需要看看數列是否是全部相異且是遞減，如果是，那麼無法達成；如果不是，那麼就可以。

程式碼:

const int _n=5e4+10;  
int t,n,m,a[_n],aa[_n];  
main(void) {ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);  
  cin>>t;while(t--){  
    cin>>n;rep(i,0,n){cin>>a[i];aa[i]=a[i];} sort(aa,aa+n,greater<int>());  
    int prev=-1;rep(i,0,n){  
      if(a[i]!=aa[i] or aa[i]==prev){cout<<"YES\n";goto A;}  
      prev=aa[i];  
    }  
    cout<<"NO\n";  
    A:;  
  }  
  return 0;  
}  

標頭、模板請點Submission看
Submission