思路
我太菜了看到这题完全没思路 所以我决定写一篇题解
题目中要求所有小朋友视野距离总和的期望值，我们可以对每一个小朋友进行单独考虑。
不难发现，第 $i$ 名小朋友的视野就是前面不比他高的小朋友的数量 $+1$，所以我们考虑第 $i$ 名小朋友前面不比他高的小朋友数量的期望。
设 $f_i$ 为不比第 $i$ 名小朋友高的期望值，那么我们可以考虑每一个不比 $i$ 高的小朋友 $j$ 能够对 $f_i$ 作出的贡献，设不比 $i$ 高的小朋友集合为 $S$ ，即我们需要求：
第 $j$ 个小朋友最多肯定只能作出 $1$ 的贡献，所以我们只需要找第 $j$ 个小朋友能够对 $f_i$ 作出贡献的概率为多少，设这个概率为 $p_i$ ，那么：
\[f_i=\sum_{j\in S}{p_j}\]那么我们来考虑 $p_i$ 怎么求。
首先 $j$ 一定是在 $i$ 前面的，且 $j$ 与 $i$ 之间必须全部都是属于集合 $S$ 里的小朋友， 否则 $i$ 就会被中间的小朋友挡住， $j$ 就无法作出贡献。
那么设集合 $S$ 的大小为 $s$， 那么除了 $j$ 以外，还剩下 $s-1$ 个不比 $i$ 高的小朋友。
因为这 $s-1$ 个小朋友在任何地方都有概率，我们可以先将其删去，这样 $j$ 与 $i$ 一定是挨在一起的， 此时还剩下 $n-(s-1)=n-s+1$ 个小朋友。
既然挨在一起，我们开始捆绑play将 $i$ 和 $j$ 看作一个整体，也就是还剩下 $n-s$ 个元素， 他们全排列的数量为 $P_{n-s}^{n-s}=(n-s)!$。
那么剩下的 $s-1$ 个小朋友我们不用考虑位置了，直接扔里面随便站就好了（误
一共有 $n$ 个小朋友，那么这 $s-1$ 个小朋友在其中的位置的排列数就是 $P^{s-1}_{n}=\frac{n!}{(n-s+1)!}$ 。
总排列数为 $P^n_n=n!$， 那么概率就为：
\[\begin{aligned} p_i&=\frac{(n-s)!\times\frac{n!}{(n-s+1)!}}{n!}\\ &=\frac{(n-s)!}{(n-s+1)!}\\ &=\frac{1}{n-s+1} \end{aligned}\]那么
\[\begin{aligned} f_i&=\sum_{j\in S}\frac{1}{n-s+1}\\ &=\frac{s}{n-s+1} \end{aligned}\]不要忘记视野为 $f_i+1$ 。
显然，对一每一个身高一样的小朋友，不比他高的小朋友的数量都是相同的，所以我们可以对每一些身高相同的小朋友一起进行计算。
设高度为 $h$ 的小朋友的数量为 $num_h$ ， 当前高度小于等于 $h$ 的小朋友数量为 $s$ ，那么答案为：
\[\begin{aligned} ans&=\sum_{h\in [1,1000]}num_h\times (f_i+1)\\ &=\sum_{h\in [1,1000]}num_h\times (\frac{s}{n-s+1}+1) \end{aligned}\]每一次处理完 $ans$ 之后再将当前的 $s$ 加上 $num_h$ 即可。
代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 301, MAXH = 1001;
int n,h[MAXN],s,num[MAXH];
double ans;
int main() {
scanf("%d", &n);
for(int i=1;i<=n;i++) {
scanf("%d", &h[i]);
num[h[i]]++;
}
for(int i=1;i<MAXH;i++) {
ans+=num[i]*(double)s/(double)(n-s+1)+num[i];
s+=num[i];
}
printf("%.2lf", ans);
return 0;
}
