UVA12004 Bubble Sort 题解

题目链接：Bubble Sort

题意：

$T \le 1000$ 组询问，每次给定 $n(1 \le n \le 10^5)$ ，

问 $1$ 到 $n$​ 的 $n$ 个数的排列中逆序对个数的期望，以分数的形式输出，比如 1/2 。

这题只有入门吗？好好好，我菜就是了，我只会 dp 。

设 $f_i$ 为 $i$ 个数的排列的逆序对个数的期望。我们考察 $i$ 的位置，则

$$f_i = \frac{1}{i}\left(f_{i-1} + 0\right) + \frac{1}{i}\left(f_{i-1} + 1\right) + \cdots + \frac{1}{i}\left(f_{i-1} + i-1\right)$$

整理一下

$$f_i = f_{i-1} + \frac{i-1}{2}$$

即（直接把每个 $f_i$ 全部写出来就能找到规律了）

$$f_i = \frac{i(i-1)}{4}$$

时间复杂度 $\mathcal{O}(T)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)())

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int qwq; cin >> qwq; 
    for(int c = 1; c <= qwq; c++) {
        int n; cin >> n;
        n = n * (n - 1); cout << "Case " << c << ": ";
        if(n % 4 == 0) cout << n / 4 << '\n';
        else if(n % 2 == 0) cout << n / 2 << '/' << 2 << '\n';
        else cout << n << '/' << 4 << '\n';
    }
    return 0;
}