为什么纯随机打乱也能过啊
查看原帖
为什么纯随机打乱也能过啊
220824
yyz1005楼主2023/12/27 14:33

这数据是否

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read(){
	ll x = 0,h = 1;
	char ch = getchar();
	while(!(ch=='-'||('0'<=ch&&ch<='9'))) ch = getchar();
	if(ch=='-') h = -1;
	else x = ch-'0';
	ch = getchar();
	while('0'<=ch&&ch<='9'){
		x = x*10+ch-'0';
		ch = getchar();
	}
	return x*h;
}
ll n,m;
const ll N = 50;
ll a[N];
const ll INF = 1e18;
double res = INF;
double V = 0.0;
priority_queue<ll,vector<ll>,greater<ll> > q;
void calc(){
	double sum = 0.0;
	while(!q.empty()){
		ll x = q.top();q.pop();
		sum = sum+(x-V)*(x-V);
	}
	res = min(res,sum);
}
int main(){
	mt19937 rng(time(0));
	n = read(),m = read();for(ll i = 1; i <= n; i++) a[i] = read(),V+=a[i];
	V = V/(double)m;
	while((double)clock()/CLOCKS_PER_SEC<=0.95){
		shuffle(a+1,a+n+1,rng);
		for(ll i = 1; i <= m; i++) q.push(0);
		for(ll i = 1; i <= n; i++) q.push(q.top()+a[i]),q.pop();
		calc();
	}
	printf("%.2lf\n",sqrt(res/(double)m));
	return 0;
}

2023/12/27 14:33
加载中...