题意
有 \(n\) 个人，\(m\) 元钱，每个人有一个最低要求工资 \(a_i\)。你需要把 \(m\) 元分成 \(n\) 份工资，每个人会随机得到一份，使得满足最低要求工资的人数期望最多。
\(n\le 1000,m\le 5000\)。
思路
考虑期望的线性性质，满足最低要求工资的人数即每个人能满足要求的概率之和，即 \(ans=\sum_{i=1}^n p_i\)。
对于每个人来说，满足条件概率即为分到大于等于 \(a_i\) 工资的概率，即 \(p_i=\frac{\sum_{j=1}^n [x_j\ge a_i]}{n}\)。
最后则有 \(ans=\frac{\sum_{i=1}^n\sum_{j=1}^n [x_j\ge a_i]}{n}\)
于是我们设 \(f_{i,j}\) 表示将 \(j\) 元钱分成了 \(i\) 份工资时 \(\sum_{i=1}^n\sum_{j=1}^n [x_j\ge a_i]\) 的最大值，且每份工资单调不递增。
假设增加了一份 \(k\) 元的工资，则该值会增加 \(\sum_{i=1}^n [a_i\ge k]\)，可以使用前缀和处理。
由于每份工资单调不递增，所以第 \(i\) 份工资的上限即为 \(\lfloor\frac{m}{i}\rfloor\)，因为要保证前面的工资都大于这份工资。
令 \(c_i=\sum_{i=1}^n [a_i\ge k]\) 于是就有：
\[f_{i,j}=\max\{f_{i-1,j-k}+c_k\} \pod{1\le i\le n,0\le j\le m,0\le k\le \min(j,\lfloor\frac{m}{i}\rfloor)}
\]
最后 \(\frac{f_{n,m}}{n}\) 即为答案，复杂度 \(O(nm\log m)\)。
代码
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n,m,c[5005];
double f[1005][5005];
signed main() {cin>>n>>m;for(int x,i=1;i<=n;i++)cin>>x,c[x]++;for(int i=1;i<=m;i++)c[i]+=c[i-1];for(int i=1;i<=n;i++){for(int j=0;j<=m;j++){for(int k=0;k<=min(j,m/i);k++){f[i][j]=max(f[i][j],f[i-1][j-k]+c[k]);}}}printf("%.15lf",f[n][m]/n);return 0;
}