题解：P10668 BZOJ2720 [Violet 5] 列队春游

cogimyun · 2025-10-10 15:19:06 · 题解

[列队春游] 题解

题意

给定整数序列 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)。

这等价于求：

x_i = \sum_{j<i} [a_j \leq a_i \text{ 并且 } j \text{ 到 } i \text{ 之间的数都小于等于 } a_i]

枚举小于 a_i 的数，则：

x_i = \sum_{k<a_i} P_k

其中 P_k 表示数 k 对 i 产生贡献的概率。

通过古典概型的方法求出 P_k。假设有 s 个小于 a_i 的数，将 k 和 a_i 绑在一起，先不考虑其他的 s-1 个小于 a_i 的数，有 (n-s)! 种排列，然后再将剩下 (s-1) 个数插进来。故概率为：

\frac{(n-s)! A_n^{s-1}}{n!} = \frac{1}{n-s+1}

因此：

x_i = \frac{s}{n-s+1}

对于每个数分别求出 x_i 即可。

算法步骤

读入 n 和数组 a
对 a 排序，得到每个 a_i 的排名，从而得到 s_i（严格小于 a_i 的数的个数）
计算 \sum_{i=1}^n \left(1 + \frac{s_i}{n-s_i+1}\right)
输出结果

复杂度分析

时间复杂度：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;
}