[列隊春游] 題解

題意

給定整數序列 \(a\)，對于隨機排列 \(p\)，求 \(\sum f_i\) 的期望。

對于位置 \(i\)，\(f_i\) 定義為最小的 \(x\)，滿足對于任意位置 \(j,1 \leq x \leq j \leq i\)，均有 \(a_{p_j} \leq a_{p_i}\)。

數據范圍：\(a_i, n \leq 10^7\)。

題解

設 \(x_i + 1\) 為第 \(i\) 位的貢獻，我們要求的是 \(\sum \mathbb{E}(x_i + 1)\)。

這等價于求：

枚舉小于 \(a_i\) 的數，則：

其中 \(P_k\) 表示數 \(k\) 對 \(i\) 產生貢獻的概率。

通過古典概型的方法求出 \(P_k\)。假設有 \(s\) 個小于 \(a_i\) 的數，將 \(k\) 和 \(a_i\) 綁在一起，先不考慮其他的 \(s-1\) 個小于 \(a_i\) 的數，有 \((n-s)!\) 種排列，然后再將剩下 \((s-1)\) 個數插進來。故概率為：

因此：

對于每個數分別求出 \(x_i\) 即可。

算法步驟

1. 讀入 \(n\) 和數組 \(a\)
2. 對 \(a\) 排序，得到每個 \(a_i\) 的排名，從而得到 \(s_i\)（嚴格小于 \(a_i\) 的數的個數）
3. 計算 \(\sum_{i=1}^n \left(1 + \frac{s_i}{n-s_i+1}\right)\)
4. 輸出結果

復雜度分析

• 時間復雜度：\(O(n \log n)\)
• 空間復雜度：\(O(n)\)

代碼實現要點

• 注意處理重復元素的情況
• 使用雙精度浮點數計算期望值并且輸出時保留兩位小數

CODE

#include<bits/stdc++.h>
using namespace std;
int n,h[305];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>h[i];
	sort(h+1,h+1+n);
	long double ans=0,pre=0;
	for(int i=1;i<=n;i++){
		if(h[i]!=h[i-1])
			pre=i-1;
		ans+=pre/(n-pre+1);
		ans++;
	}
	cout<<fixed<<setprecision(2)<<ans;
	return 0;
}