模拟退火 WA 求助
查看原帖
模拟退火 WA 求助
542128
liyixin0514楼主2024/11/11 22:00

rt,改了很多参数依然正确率很低,大概只有 10pts10pts。萌新刚学模拟退火 1ms,求问是这份代码有误还是参数不合适?有没有修改建议?拜谢 orz

#include<bits/stdc++.h>
#define sf scanf
#define pf printf
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
using namespace std;
typedef long long ll;
namespace characteristic {
	constexpr int N=25;
	constexpr double T=1e5,delta=0.98,eps=1e-10,time_limit=0.99;
	int n,m;
	int a[N];
	mt19937 rd(random_device{}());
	double tem;
	double ans;
	int sum[N];
	double de;
	struct myst {
		int x;
		bool operator < (const myst b) const { return sum[x] > sum[b.x]; }
	};
	double calc () {
		memset(sum,0,sizeof(int)*m);
		priority_queue<myst> que;
		rep(i,0,m-1) que.push({i});
		rep(i,1,n) {
			int x=que.top().x;
			que.pop();
			sum[x]+=a[i];
			que.push({x});
		}
		double s=0;
		rep(i,0,m-1) s+=((1.0*sum[i]-de)*(1.0*sum[i]-de));
		s/=m;
		return s;
	}
	void swap(int &x,int &y) { x^=y, y^=x, x^=y; }
	void sa() {
		tem=T;
		while(tem>eps) {
			int x=rd()%n+1,y=rd()%n+1;
			swap(a[x],a[y]);
			double now=calc();
			if(now<ans) ans=now;
			else if(exp(now-ans)>tem*rand()/RAND_MAX) swap(a[x],a[y]);
			tem*=delta;
		}
	}
	void main() {
		clock_t st=clock();
		srand(random_device{}());
		sf("%d%d",&n,&m);
		rep(i,1,n) sf("%d",&a[i]), de+=a[i];
		de/=m;
		ans=T;
		while(clock()-st < time_limit*CLOCKS_PER_SEC) sa();
		pf("%.2lf\n",sqrt(ans));
	}
}
int main() {
    #ifdef LOCAL
    freopen("in.txt","r",stdin);
    freopen("my.out","w",stdout);
    #endif
	characteristic :: main();
}
2024/11/11 22:00
加载中...