BZOJ2720: [Violet 5]列队春游 【概率与期望】

题意自行理解,先讲一下概率和期望怎么算

概率

概率准确的定义自行百度，这里就不赘述了

概率的计算其实很简单，就是将符合条件的情况除以总共的情况

下面以掷骰子为例：

问题：将一个骰子掷出，$6$朝上的概率是多少

解决

很显然的，将一个骰子掷出，一共就只有$6$种情况，分别是 :

$1$朝上，$2$朝上，$3$朝上，$4$朝上，$5$朝上，$6$朝上

我们要求的是$6$朝上的概率，不难看出，上述符合$6$朝上的情况只有一种

那么我们的概率就是

$$P=\frac{1}{6}$$

期望

关于期望的详细计算可以看这位大佬的文章 知乎传送门

说的简单一点，期望就是算加权平均数，用当前情况的值乘上当前情况的概率，然后把所有的值都加起来除以1（因为每种情况的概率之和必为1）

回到题目

这道题目仔细思考之后其实会发现，可以用每一个小朋友的期望值之和加起来求得

求解每一个小朋友的期望值

我们设$k$为所有身高大于等于当前小朋友的人数之和（不包括自身）

然后枚举当前小朋友的视野长度$L$

考虑比当前小朋友高的人的站位

那么在这个小朋友前面的$L$个位置都不能站比当前小朋友高的人，那么比小朋友高的$k$个人一共有$n-L$个位置可以放，考虑排列顺序，则共有$A_{n-L}^k$种放法

考虑当前小朋友的位置

因为视野长度为$L$，所以当前小朋友前面必须要预留出$L$个位置给比他矮的小朋友站，所以当前小朋友必须要从$L+1$的位置开始排，所以当前小朋友有$(n-L+1)$种站位

开始计算

根据乘法原理，符合要求的状况一共有$A_{n-L}^k\ast (n-L+1)$种

总共的情况就很好计算了，就是$A_{n-L}^k$

所以当前小朋友的期望值就是
$$Ans=\sum _{L=1}^n\frac{A_{n-L}^k\ast (n-L+1)}{A_{n-L}^k}$$

最后化简得出
$$Ans=\frac{k+2}{n+1}$$

推导过程看这个大佬
说白了就是不想打公式

$Code$

#include <bits/stdc++.h>using namespace std;int h[1010],sum,n;
double ans = 0;
int main(){cin >> n;for(int i = 1; i <= n; i++){int a;cin >> a;h[a]++;}	for(int i = 1; i <= 1000; i++){ans += 1.0*h[i] * (n+1) / (n - sum+1);sum += h[i];//类似前缀和，计算比当前小朋友矮的人数 }cout << fixed << setprecision(2) << ans;return 0;
}