模拟退火求助
查看原帖
模拟退火求助
690333
qinghaipeng楼主2023/10/19 16:38

虽然说我也不知道为什么我会用这么答辩的写法

#include<iostream>
#include<cstdio>
#include<iomanip>
#include<memory.h>
#include<cstdlib>
#include<ctime>
#include<climits>
#include<cctype>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<bitset>
#include<map>
#include<unordered_map>
#include<stack>
#include<vector>
#include<queue>
#include<deque>
#include<list>
#include<utility>
//#include<Windows.h>
#define bug puts("liupei")
#define int long long
#define F(i,j,n) for(register int i=j;i<=n;++i)
#define R(i,j,n) for(register int i=j;i>=n;--i)
#define pii pair<int,int>
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define lc (p<<1)
#define rc (p<<1|1)
#define rd (rand()*(rand()%100))
using namespace std;
const int N=2e5+10;
const bool debug=0;
int T,n,b[N],ans;
double MAX_TIME=0.98;
struct person{
	int c,aid,r;
}a[N];
inline int calc(int v[]) {//计算一种排列 b 的价值 
	register int sum=0;
	F(i,1,n){
		if(a[i].aid==v[i]){
			continue;
		}else if(a[i].aid>v[i]){
			sum+=a[i].c;
		}else{
			sum-=a[i].c;
		}
	}
	return sum;
}
inline void fire(){//模拟退火 
	register double t = 10000.0;//温度 
	
	register int nx=0,ny=0;
	
	register int tmp[N];
	F(i,1,n)tmp[i]=b[i];
	while (t > 0.0001) {
		
		if(nx==ny){
			nx=rd%n+1;
			ny=rd%n+1;//1~n 随机整数 
//			printf("%lld %lld\n",nx,ny);
		}
		swap(tmp[nx],tmp[ny]);

		//随机交换两个不同位置数,然而试了一下效果并不好,但是下面的随机打乱序列效果更不好 
		//扰动当前状态 
//		random_shuffle(tmp+1,tmp+1+n);
	    int delta = calc(tmp) - calc(b);
	    if (delta>0 || (exp(-delta / t) > rand())) {//解更优 
	    	F(i,1,n)b[i]=tmp[i];
		}
	    t *= 0.985;
	    
	    nx=ny=0;

	}
	int cb=calc(b);
	ans=max(ans,cb);
	return;
}
signed main(){
	srand(time(0));
	if(debug){
		freopen("3.in","r",stdin);
	}
	scanf("%lld",&T);
	MAX_TIME/=double(T*1.0);//每个测试点只能用的时间 
	register double TTT=0.0;
	while(T--){
		scanf("%lld",&n);
		F(i,1,n){
		    scanf("%lld",&a[i].r);
		    a[i].aid=n-i+1;//等级分排名按等级分从大到小排序 
		    b[i]=a[i].aid;//初始答案,最贴近原序列 
		}
		F(i,1,n)scanf("%lld",&a[i].c);
		ans=0;//由于是最大化,所以初始值是最小
//		cout<<"CALC(B)="<<calc(b)<<"\n";

		while (((double)clock()-TTT)/1000.0 < (MAX_TIME)) fire();
		TTT=clock();//当前使用了的时间 
		
		if(debug)printf("ANS=");
		printf("%lld\n",ans);
		if(debug){
			printf("最优的答案序列:\n");
			printf("b[]: ");
			F(i,1,n)cout<<b[i]<<' ';
			cout<<"CALC(B)="<<calc(b)<<"\n"; 
		}
		if(debug)puts("\n");
	}
	return 0;
}

全 WA ,是参数需要调还是说完全就不能用(()())

2023/10/19 16:38
加载中...