Hint1

本题中将书籍整理有序(升序),且每次只能整理相邻的书籍与哪一类排序算法非常相似？

Hint2

如何证明冒泡排序次数就是任意交换策略中交换次数最少即最优的解法之一？

Solution

本题考察 冒泡排序的交换次数

冒泡排序具有如下几个很明显的性质:

1. 冒泡排序每次交换一定是交换相邻的元素

2. 交换一次逆序对必然减少一个,直到整个数组逆序对为0,逆序对即序列中任意两对数满足 $a > b$ 的个数,例如 $3,2,1$ 有 $3$ 个逆序对,分别是$(3,2) , (3,1) , (2,1)$。

3. 冒泡排序中需要交换的总次数是整个数组的逆序对(如 $2$ 中介绍的例子)

4. 冒泡排序中对于某个数需要交换的次数是对于它来说在这个数组中的逆序对数

为什么会说结论 $3$ 是因为求逆序对有两大经典算法可以做到复杂度 $O(nlog(n))$ ,但本题是可以接受复杂度 $O(n^2)$ ,因此针对本题直接写冒泡排序计算交换次数即可！有兴趣的同学可以在网上自行学习两大经典求逆序对算法(归并排序求逆序对,树状数组求逆序对)

C++代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define inf 0x3f3f3f3f3f3f3f3f
typedef pair<int, int> PII;

void solve() {
    int n,cnt=0;
    cin >> n;
    vector<int> a(n + 10);
    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]);
                cnt++;
            }
        }
    }
    cout << cnt << endl;
}
signed main() {
    int t = 1;
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    //	cin>>t;
    while (t--) solve();
    return 0;
}