Codeforce 1420 A. Cubes Sorting 決議(思維)
今天我們來看看CF1420
題目連結
題目
給一個數列\(a\)，求能不能在不超過\(\frac{n(n-1)}{2}-1\)次相鄰元素的調換下，得到遞增數列，
前言
觀看更多正版原始文章請至petjelinux的blog
想法
注意到，這是\(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
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/122753.html
標籤：其他
上一篇：計算機基礎資料結構講解第十一篇-字串模式匹配KMP演算法第一講
下一篇：高數問題