AtCoder 0. 随机化贪心
原题链接
简单
作者:
流动的音符
,
2023-12-11 12:03:02
,
所有人可见
,
阅读 60
/*通过观察能发现这是一个贪心,
值越接近答案越小, 我们可以把每个数加到当前和最小的组里,然后通过随机化 进行多次贪心,
随机化的次数可以稍微多点。每次贪心把序列打乱, 然后多次进行操作获得对应的值,从中取最小值就可以了。
*/
#include <bits/stdc++.h>
using namespace std;
int n, d, w[20], b[20], t = 2000000;
double ans = 1e18, sum = 0;
signed main() {
cin >> n >> d;
for (int i = 1; i <= n; i++) {
cin >> w[i];
sum += w[i];
}
double avg = sum / d;
while (t--) {
memset(b, 0, sizeof(b));
random_shuffle(w + 1, w + n + 1);//从位置 w + 1 到 w + n + 1 的范围内的元素将被随机排列。
int k = 1;
sum = 0;
for (int j = 1; j <= n; j++) {
for (int i = 2; i <= d; i++) {
if (b[i] < b[k]) k = i;
}
b[k] += w[j];//加到d个数组中数据最小的地方
k = 1;
}
for (int i = 1; i <= d; i++) sum += (avg - b[i]) * (avg - b[i]);
sum = sum / d;
ans = min(ans, 1.0 * sum);
}
printf("%.15lf", ans);
return 0;
}