大佬教程收集整理的这篇文章主要介绍了列队春游，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。

列队春游

一道好题(花了三天时间才弄懂TAT)

题目描述

输入格式

输出格式

样例输入

3
1 2 3

样例输出

4.33

样例说明及数据范围

历经千辛万苦,翻了20多题解,最终在wyx大佬的帮助下终于看明白了式子

首先，要计算总视野期望，可以把每一个人的视野期望算出来，然后求和

于是考虑如何计算每个人的视野期望,这里有两个思路:

思路1

根据期望的线性性，枚举每种可能的视野，把期望分解成 每种视野的视野长度 * 该种视野的概率

就是$\sum _{i=1}^{n}i\times P(i)$

我们可以用一张图来理解

上面的公式相当于每次加1列,我们可以转化为每次加1行,就是$\sum _{i=1}^{n}P(L>=i)$

在考虑概率如何计算,设不小于第i个小朋友身高的有k个人（不包括他自己），那么

会挡住小朋友的人包括自己随便放总共有$A_n^{k+1}$种情况，其中那些会挡住小朋友的人不能放在小朋友前面的i-1个位置，也不能放在小朋友的位置，所以方案数为$A_{n-i}^k$,然后又因为小朋友自己有n-i+1个位置可以放，所以乘上一个n-i+1

然后就推式子嘛（我不会）

思路2

设身高<i的人有s个，那么$$ans={\displaystyle \frac{s\times (n-s)!\times A_n^{s-1}}{n!}}+1$$

每次将一个比i矮的人与i捆绑,则有s种方案，

然后将剩下的s-1个人在n个位置里放，有$A_n^{s-1}$种方案，

再将n-s个人(包括i和捆绑的这个人)放到剩下的位置里，有m!种方案，

这样算出来就是站在i前面的那个人会让i视野距离+1的方案数,也就是$s\times (n-s)!\times A_n^{s-1}$

那么i的视野距离+1的概率就是$\frac{s\times (n-s)!\times A_n^{s-1}}{n!}$

然后就展开式子就OK了

$$ans={\displaystyle \frac{s\times (n-s)!\times A_n^{s-1}}{n!}}+1$$

$$ans={\displaystyle \frac{s\times (n-s)!\times \frac{n!}{(n-s+1)!}}{n!}}+1$$

$$ans={\displaystyle \frac{s\times (n-s)!}{(n-s+1)!}}+1$$

$$ans={\displaystyle \frac{s\times (n-s)!}{(n-s+1)\times (n-s)!}}+1$$

$$ans={\displaystyle \frac{s}{(n-s+1)}}+1$$

$$ans={\displaystyle \frac{n+1}{n-s+1}}$$

#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
#define db double
inline int in(){
    int x = 0;
    bool f = 1;
    char c = getchar();
    while(c > '9' || c < '0'){
        if(c == '-') f = 0;
        c = getchar();
    }
    while(c <= '9' && c >= '0'){
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    if(f) return x;
    else return -x;
}
//设身高>=i的有m个人(包括i),<i的有s个人
//第i个人的期望视野距离为ans[i] = s*m!*A(n,s-1)/n! + 1
//每次将一个比i矮的人与i捆绑,则有s种方案
//将剩下的s-1个人在n个位置里全排列
//再将m个人(包括i和捆绑的这个人)全排列放到剩下的位置里
//这样算出来就是站在i前面的人会让i视野距离+1的方案数,也就是s*m!*A(n,s-1)
//那么i的视野距离+1的概率就是s*m!*A(n,s-1)/n!
//ans[i] = s*m!*A(n,s-1)/n! + 1
//       = (s * (n-s)! * n!/(n-s+1)!) / n! + 1
//       = s * (n-s)! / (n-s+1)! + 1
//       = s * (n-s)! / (n-s+1)*(n-s)! + 1
//       = s/(n-s+1) + 1
//       = (n+1)/(n-s+1)
const int N = 310;//n <= 300
const int M = 1010;//h <= 1000
int n;
int h[M];
int s;
double ans;
int main(){
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
    n = in();
    int x;
    for(int i = 1;i <= n;++i){
        x = in();
        h[x]++;
    }
    for(int i = 1;i <= 1000;++i){
        if(!h[i]) continue;
        ans = ans + (db)(n+1)/(n-s+1)*h[i];//h[i]个人身高都为i
        s += h[i];
    }
    printf("%.2lf",ans);
    return 0;
}

大佬总结

以上是大佬教程为你收集整理的列队春游全部内容，希望文章能够帮你解决列队春游所遇到的程序开发问题。

如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。