提交时间:2024-10-02 13:52:03

运行 ID: 32881

#include <bits/stdc++.h> #define int long long using namespace std; int n, m, qzd[1005], c0; long double f[1005][5005]; int a[1005]; signed main() { //freopen("monster.in", "r", stdin), //freopen("monster.out", "w", stdout); scanf("%lld %lld", &n, &m); c0 = n; for (int i = 1; i <= n; i++) { scanf("%lld", &a[i]); } sort(a + 1, a + n + 1, greater <int>()); for (int i = 1; i <= n; i++) { if (a[i] == 0) { n = i - 1; break; } } for (int i = 1; i <= c0; i++) { if (a[i] == a[i - 1]) qzd[i] = qzd[i - 1] + 1; else qzd[i] = 0; f[i][0] = i * 1.0 * n / c0; for (int j = 1; j <= m; j++) { f[i][j] = f[i - 1][j] + 1.0 * n / c0; if (j >= a[i]) f[i][j] = min(f[i][j], f[i][j - a[i]] - 1.0 * n / c0 + (i - 1 - qzd[i]) * 1.0 / c0); } } printf("%.9Lf", f[c0][m]); return 0; }