• 欢迎光临~

# 列队春游

### 样例输入

``````3
1 2 3``````

### 样例输出

``4.33``

### 思路1

$ans=\sum _{i=1}^{n}\frac{\left(n-i+1\right){A}_{n-i}^{k}}{{A}_{n}^{k+1}}$

### 思路2

$ans=\frac{s×\left(n-s\right)!×{A}_{n}^{s-1}}{n!}+1$

$ans=\frac{s×\left(n-s\right)!×\frac{n!}{\left(n-s+1\right)!}}{n!}+1$

$ans=\frac{s×\left(n-s\right)!}{\left(n-s+1\right)!}+1$

$ans=\frac{s×\left(n-s\right)!}{\left(n-s+1\right)×\left(n-s\right)!}+1$

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

$ans=\frac{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;
}``````