题解 P1116 【车厢重组】

Skyjoy · 2019-10-08 21:31:06 · 题解

显而易见，这道题要按照题意操作排序，只能冒泡了。

给不懂的童鞋简单解释一下：

有些童鞋可能审题不够清晰，会想到快排、归并、桶、堆排等神奇的排序算法。然鹅我们思考一下各种排序算法的实现思想，发现一件神奇的事情：

好像只有冒泡能够使排序时相邻两个交换了

看了看大部分的题解，直接模拟了整个过程并计数。但是，毕竟冒泡中，该浮上去的早晚都要浮上去，不用模拟，直接计数即可。

接下来就是最激动人心的代码了：

#include<bits/stdc++.h>
using namespace std;
int n,cnt=0,a[10010];
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<i;j++){
            if(a[j]>a[i]){
                cnt++;
            }
        }
    }
    cout<<cnt;
    return 0;
}

祝童鞋们CSP2019rp++！！！