萌新刚学SA求调
查看原帖
萌新刚学SA求调
448018
KAqwq楼主2024/8/11 15:27
#include <bits/stdc++.h>
#include <random>
#define dt 0.997
#define seed 216222903

typedef long long LL;
typedef double d;

LL n, m;
LL a[25], pos[25];
d q, ans = 0x3f;

inline d ask() {
	LL rq;
	d res = 0;
	for (LL i = 1; i <= n; ++i) {
		ans = 0x3f;
		for (LL j = 1; j <= m; ++j) { if (pos[j] < ans) ans = pos[j], rq = j;}
		pos[rq] += a[i];
	}
	for (LL i = 1; i <= m; ++i) {
		res += (q - pos[i]) * (q - pos[i]);
	}
	return sqrt(res / m);
}
inline void SA() {
	d t = seed;
	while (t > 1e-14) {
		LL lq = rand() % n + 1, rq = rand() % n + 1;
		std::swap(pos[lq], pos[rq]);
		d good_ans = ask();
		if (good_ans < ans) ans = good_ans;
		else if (exp((good_ans - ans) / t) < rand() / RAND_MAX) std::swap(pos[lq], pos[rq]);
		t *= dt;
	}
}
inline void solve() {
	LL T = 5;
	while (T--) {SA();}
}

int main() {
	srand(seed);
	std::cin >> n >> m;
	for (LL i = 1; i <= n; ++i) std::cin >> a[i], q += a[i]; 
	q /= m;
	solve();
	std::cout << std::fixed << std::setprecision(2) << ans;
	return 0;
}
2024/8/11 15:27
加载中...