rt,改了很多参数依然正确率很低,大概只有 10pts。萌新刚学模拟退火 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();
}