• 欢迎光临~

列队春游

开发技术 开发技术 2022-05-30 次浏览

列队春游

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

题目描述

列队春游

输入格式

列队春游

输出格式

列队春游

样例输入

3
1 2 3

样例输出

4.33

样例说明及数据范围

列队春游

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

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

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

思路1

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

就是 i = 1 n i × P ( i )

我们可以用一张图来理解

列队春游

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

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

a n s = i = 1 n ( n i + 1 ) A n i k A n k + 1

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

然后就推式子嘛(我不会

列队春游

思路2

设身高<i的人有s个,那么 a n s = s × ( n s ) ! × A n s 1 n ! + 1

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

然后将剩下的s-1个人在n个位置里放,有 A n s - 1 种方案,

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

这样算出来就是站在i前面的那个人会让i视野距离+1的方案数,也就是 s × ( n s ) ! × A n s 1

那么i的视野距离+1的概率就是 s × ( n s ) ! × A n s 1 n !

然后就展开式子就OK了

a n s = s × ( n s ) ! × A n s 1 n ! + 1

a n s = s × ( n s ) ! × n ! ( n s + 1 ) ! n ! + 1

a n s = s × ( n s ) ! ( n s + 1 ) ! + 1

a n s = s × ( n s ) ! ( n s + 1 ) × ( n s ) ! + 1

a n s = s ( n s + 1 ) + 1

a n s = n + 1 n s + 1

AC代码

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

 

程序员灯塔
转载请注明原文链接:列队春游
喜欢 (0)