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

· · 题解

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;
}