提交时间:2024-10-02 16:24:56

运行 ID: 32963

#include<iostream> #include<algorithm> #include<cstring> using namespace std; #define int long long const int N=1010,M=5100; int n,m,a[N],f[2][N][M]; int g[M]; inline int count(int k){return n-(upper_bound(a+1,a+n+1,k)-a)+1;} void init(){ cin>>n>>m; for(int i=1;i<=n;i++)cin>>a[i]; sort(a+1,a+n+1); for(int i=0;i<=m;i++)g[i]=count(i); } signed main(){ // freopen("monster.in","r",stdin); // freopen("monster.out","w",stdout); init(); memset(f,0x3f,sizeof(f)); f[0][0][0]=0; for(int i=m;i>=0;i--){ for(int j=0;j<=n&&i*j<=m;j++){ for(int t=0;t<=m;t++){ f[1][j][t]=f[0][j][t]; if(t>=i&&j>=1)f[1][j][t]=min(f[1][j][t],f[1][j-1][t-i]+g[i]); } } for(int j=0;j<=n&&i*j<=m;j++){ for(int t=0;t<=m;t++){ f[0][j][t]=f[1][j][t]; f[1][j][t]=0x3f3f3f3f; } } } printf("%.10f",(double)f[0][n][m]/n); return 0; }