UVA12004 Bubble Sort 题解

5k_sync_closer · 2021-12-09 11:31:11 · 题解

题意：给 n 个数冒泡排序，求期望交换次数。

思路

这个题目可以转化为求 n 个数的期望逆序对个数。

那么，n 个数有 C_n^2=\dfrac{n(n-1)}2 组数对，

又因为有这句话：虽然没什么影响

每个数不同，那么一对数就有 \dfrac12 的几率是逆序对，

所以期望逆序对数就是 \dfrac{n(n-1)}2×\dfrac12=\dfrac{n(n-1)}4 对。

注意分数。

代码

#include <iostream>
#define int long long
using namespace std;
int n;
signed main()
{
    cin >> n;
    for (int i = 1, t, ans; i <= n; ++i)
    {
        cin >> t;
        ans = t * (t - 1) / 2;
        if (ans % 2) cout << "Case " << i << ": " << ans << "/2" << endl;
        else cout << "Case " << i << ": " << ans / 2 << endl;
    }
    return 0;
}