题解：P1116 车厢重组

· · 题解

题目传送门

题意概括

输入一个序列a，要求求出将序列a从小到大排序的次数。

分析

标准逆序对。
如果a_i>a_j且i<j，则这两个数称为逆序数。
利用冒泡排序，由于n \le 10000，复杂度为O(n^2)，所以不会超时。

代码

#include<bits/stdc++.h>
using namespace std;
int n,t,s=0,a[10001];
int main(){
    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]){
                swap(a[j],a[j+1]);
                s++;
            }
        }
    }
    cout<<s;
    return 0;
}

::::warning[注意] 不要超题解。本蒟蒻就是超题解棕名的 :::: ::::warning[球球了] 能通过吗 QWQ ::::