Codeforces #1420A Cubes Sorting

문제

https://codeforces.com/problemset/problem/1420/A

걸린 시간

00 : 43 : 00 실패

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
typedef long long ll;
using namespace std;

int n;
vector<int> a;

void solve(){
    for(int i = 0; i < n-1; i++){
        if(a[i] <= a[i+1]){
            cout << "YES\n";
            return;
        }
    }
    cout << "NO\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tc;
    cin >> tc;
    while(tc--){
        cin >> n;
        a.resize(n);
        for(auto& i : a) cin >> i;
        solve();
    }
    return 0;
}

두개의 이웃한 큐브들을 교환하는 횟수가 n(n-1)/2-1 를 넘기지 말아야 한다는 설명에서 버블정렬을 떠올릴 수 있어야 한다.

자료가 역순으로 정렬되어 있는 버블정렬의 최악의 경우에서는 교환횟수가 n(n-1)/2-1 를 초과하게 된다.