A. Cubes Sorting 解析(思維)
2024-09-07 23:05:18
Codeforce 1420 A. Cubes Sorting 解析(思維)
今天我們來看看CF1420
題目連結
題目
給一個數列\(a\),求能不能在不超過\(\frac{n(n-1)}{2}-1\)次相鄰元素的調換下,得到遞增數列。
前言
想法
注意到,這是\(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
最新文章
- 记一次nginx部署yii2项目时502 bad gateway错误的排查
- PostSharp-4.3.22安装包_KeyGen发布
- table的遍历
- adroid 目录
- 修改ubuntu DNS的步骤/wget url报错: unable to resolve host address的解决方法
- 3163: [Heoi2013]Eden的新背包问题
- 实例化spring容器
- linux的Ubuntu
- mapper配置
- nginx-url重写
- 常用machine learning数据集
- Java EE (10) - 资源服务器的整合
- ngx.re.match
- toLatin1 qt
- 2sat
- Mysql复制一个数据库到另一个数据库
- Light OJ 1009
- 2D空间的OBB碰撞实现
- Luogu1084 NOIP2012D2T3 疫情控制 二分答案、搜索、贪心、倍增
- Initialization of bean failed; nested exception is java.lang.IllegalArgumentException: error at ::0 inconsistent binding