Acwing3715. 最少交换次数（冒泡排序法的模拟思路）

给定一个 1∼N 的随机排列，要求一次只能交换相邻两个数，那么最少需要交换多少次才可以使数列按照从小到大排列呢？

请你求出一个待排序序列的最少交换次数和对应的逆序数列。

逆序数列：给定 n 个数 1,2,…,n 的一个排列 a1a2…an，令 bi 是数 i 在此排列中的逆序数，换句话说，bi 等于该排列中先于 i 又大于 i 的那些数的个数。数列 b1b2…bn 称为排列 a1a2…an 的逆序数列(inversion sequence)。

输入格式

第一行一个整数 N。

第二行一个 1∼N 的排列。

输出格式

第一行输出逆序数列，数之间用空格隔开。

第二行输出最少交换次数。

数据范围

1≤N≤1000

输入样例：

8
4 8 2 7 5 6 1 3

输出样例：

6 2 5 0 2 2 1 0
18

要让数列有序， 逆序对中的元素必然直接或间接变换相对位置， 而题目中只能相邻元素交换 ，因此每次交换最多只能消除一个逆序对 所以最小交换次数即逆序对的数量(逆序数列的和) 

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e3 + 10;

int n, res;
int a[N], b[N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j < i; ++j)
            if (a[j] > a[i])
                b[a[i]]++;
    for (int i = 1; i <= n; ++i)
        printf("%d ", b[i]), res += b[i];
    printf("\n%d\n", res);
    return 0;
}

 

算法思路
对于第一个小问题，直接暴力模拟冒泡排序。
对于第二个小问题，现在数组中找到对应的数字，然后纯枚举即可。

时间复杂度
冒泡排序复杂度是O(n^2)的。找到数字和枚举都是线性的，加上序列枚举，在O(n^2)左右。综上，时间复杂度为O(n^2)。