脚本宝典收集整理的这篇文章主要介绍了列队春游,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
一道好题(花了三天时间才弄懂TAT)
3
1 2 3
4.33
历经千辛万苦,翻了20多题解,最终在wyx大佬的帮助下终于看明白了式子
首先,要计算总视野期望,可以把每一个人的视野期望算出来,然后求和
于是考虑如何计算每个人的视野期望,这里有两个思路:
根据期望的线性性,枚举每种可能的视野,把期望分解成 每种视野的视野长度 * 该种视野的概率
就是
我们可以用一张图来理解
上面的公式相当于每次加1列,我们可以转化为每次加1行,就是
在考虑概率如何计算,设不小于第i个小朋友身高的有k个人(不包括他自己),那么
会挡住小朋友的人包括自己随便放总共有种情况,其中那些会挡住小朋友的人不能放在小朋友前面的i-1个位置,也不能放在小朋友的位置,所以方案数为,然后又因为小朋友自己有n-i+1个位置可以放,所以乘上一个n-i+1
然后就推式子嘛(我不会)
设身高<i的人有s个,那么
每次将一个比i矮的人与i捆绑,则有s种方案,
然后将剩下的s-1个人在n个位置里放,有种方案,
再将n-s个人(包括i和捆绑的这个人)放到剩下的位置里,有m!种方案,
这样算出来就是站在i前面的那个人会让i视野距离+1的方案数,也就是
那么i的视野距离+1的概率就是
然后就展开式子就OK了
#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,请注明来意。