大叔都喜欢学妹，但是在新生报道的时候，学妹到达的顺序是随机的，每个学妹只能在见面的时候决定是否和她搭讪，而且只能选择一个学妹，你决定，总是放弃前\(K\)个学妹，同时记下学妹中质量最高的那个，之后，一旦遇到一个质量比前\(K\)个学妹都要高的学妹，就和她搭讪
求搭讪到的学妹质量最高的概率最大时\(K\)的取值。
首先，这显然是个结论题，答案差不多就是\(frac{N}{e}\)，之后处理一下进位就是
当然，我们也可以暴力计算
假设\(N\)出现在第\(x(>K)\)个，前\(x-1\)个的最大值为\(M\)
则它的概率就是\(\frac{A_{M-1}^{x-1}A_{N-x}^{N-x}\times K}{N!}\)
枚举\(x,M\)，求和，找和最大的\(K\)即可
AC-Code
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100 + 5;
double p[maxn][maxn];
double f[maxn];
double calc(int k , int n)
{
double ret = 0;
for (int m = k ; m < n ; m++)
for (int x = 0 ; k + x <= m ; x++)
ret += p[m - 1][k + x - 1] * f[k + x - 1] * k * f[n - (k + x + 1)];
return ret;
}
int main()
{
p[0][0] = 1;
for (int i = 1 ; i < maxn ; i++)
{
p[i][0] = 1;
for (int j = 1 ; j < maxn ; j++)
p[i][j] = p[i - 1][j] + p[i - 1][j - 1];
}
f[0] = 1;
for (int i = 1 ; i < maxn ; i++)
{
f[i] = f[i - 1] * i;
}
int n , x;
cin >> n;
double ans = 0;
for (int i = 1 ; i <= n ; i++)
{
double tans = calc(i , n);
if (tans > ans)
{
x = i;
ans = tans;
}
}
cout << x << endl;
return 0;
}