自动搬运

查看原文

来自洛谷，原作者为

	Pursuing_OIer Expected Yes , got YES.

搬运于2025-08-24 23:00:05，当前版本为作者最后更新于2024-07-01 14:11:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

BZOJ2720 [Violet 5] 列队春游 题解

Problem

对于一个数列 $S$，$S_0= \infty$，设对于 $S_i$，$S_{a_i}$ 是 $S_i$ 之前第一个大于等于 $S_i$ 的数。给定 $S$ 中的元素，求 $\sum_{i=1}^{n}(i-a_i)$ 的期望。

Solution

我们考虑对于每一种身高的学生，分别统计期望。显然，对于身高为 $h$ 的学生，只有身高为 $h-1$ 及以下的学生可以产生贡献，且每个人产生的贡献都是 $1$。
设对于当前的 $h$，共有 $s$ 个可以产生贡献的学生，剩下便有 $n-s$ 个学生（包括当前索要贡献的学生）。这些学生之间共 $n-s+1$ 个空。而一个学生想要产生贡献，就必须恰好站在索要贡献的学生之前的空里，贡献为 $\frac{1}{n-s+1}$ 。若身高为 $h$ 的学生共有 $b$ 个，则此类学生对所有身高为 $h$ 的学生所产生的贡献为 $\frac{s \times b}{n-s+1}$。
另外，每个人不论如何都有 $1$ 的贡献，应当加上。
实现时，可以记录每种身高学生的个数并依次累加贡献，时间复杂度为基于身高值域的线性复杂度。

Code

#include<bits/stdc++.h>
using namespace std;
int n,a,b[2000],sum,maxn;
double ans;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a);
		++b[a];
		maxn=max(maxn,a);
	}
	for(int i=1;i<=maxn;++i){
		ans+=1.0*sum*b[i]/(n-sum+1)+b[i];
		sum+=b[i];
	}
	printf("%.2lf",ans);
	return 0;
}