CF1420A Cubes Sorting——蒟蒻题解

吐槽：刚看到这题几分钟就想到了正解，然后发现这次cf没报名，悲痛万分之后来给大家发题解

题目大意

给定n个立方体的体积，问是否可以通过最多$\frac{n?(n?1)}{2}?1$次操作，（每次操作可以交换两个相邻的数）将数列按从小到大排序（非严格大于）

题目思路：

一看就知道是个找规律题，我们可以从最坏的例子入手，看看与题目描述的操作次数有没有规律

假设有这样一种最坏情况

5 4 3 2 1

可以手写一个冒泡来计算操作次数（也可以自己口胡

查询排序次数的冒泡代码：

int main(){
    int a[1005];int n;cin>>n;for(int i=1;i<=n;i++){
    cin>>a[i];}for(int i=1;i<=n-1;i++){
    for(int j=1;j<=n-i;j++){
    if(a[j]>a[j+1]){
    int x=a[j];a[j]=a[j+1];a[j+1]=x;ans++;}	}}cout<<ans;
}

不管口胡还是写程序，我们都可以得出给这种排列排序需要$10$次交换，刚好比规定的（$\frac{5?(5?1)}{2}?1$）多$1$

而次劣情况

5 4 3 1 2

就已经是在范围内的了（9次）

所以

只要不是最劣情况都可以在要求范围内排序成功

ps:你也可以自己多试几次来确认这个规律

所以这题就能很简单的做出来了

简单的代码

#include<bits/stdc++.h>
using namespace std;
int a[500004];
int main(){
    int t;cin>>t;while(t--){
    int n;cin>>n;int x=false;for(int i=1;i<=n;i++){
    cin>>a[i];}if(n<=2&&a[2]<a[1]){
    //这里我确保没问题特判了一下n小的情况，不要应该也行cout<<"NO"<<endl;continue;}for(int i=2;i<=n;i++){
    if(a[i]>=a[i-1]){
    x=true;}}if(x)cout<<"YES"<<endl;elsecout<<"NO"<<endl;}}