求助
查看原帖
求助
676668
SkokraFX楼主2025/1/17 17:54

以下代码有时会不跑SA是什么回事啊,而且0分:

#include<bits/stdc++.h>
using namespace std;
#define down 0.997
#define N 1000005
int a[N];
int n,m,len;
double ans=1e9;
double as=0.0;
double solve(){
	int q[25]={0},w,cnt;
	double sum=0;
	for(int i=1;i<=n;i++){
		cnt=0x3f3f3f3f;
		for(int j=1;j<=m;j++){
			if(q[j]<cnt){
			    cnt=q[j];
			    w=j;
			}
		}
		q[w]+=a[i];
	}
	for(int i=1;i<=m;i++){
		sum+=(as-q[i])*(as-q[i]);
	}
	return sqrt(sum/m);
}
void SA(){
    double tem=10000;
    while(tem>1e-12){
    	int ex,ey;
		do{
			ex=rand()%n+1;
			ey=rand()%n+1;
		}while(ex==ey);
        swap(a[ex],a[ey]);
        int ew=solve();
        int del=ew-ans;
        if(del<0){
            ans=ew;
        }
        else if(exp(-1.0*del/tem)*RAND_MAX>rand()){
            swap(a[ex],a[ey]);
        }
        tem*=down;
    }
}
int main(){
    scanf("%d%d",&n,&m);
    len=n/m;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
		as+=a[i];
    }
    sort(a+1,a+n+1);
    as/=m;
    while((double)clock()/CLOCKS_PER_SEC<0.99) SA();
    printf("%.2lf",ans);
}
2025/1/17 17:54
加载中...