35pts求助模拟退火
查看原帖
35pts求助模拟退火
285617
黑影洞人楼主2022/7/21 16:31
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<cstring>
#define N 114514
#define int long long
using namespace std;
int xxx,yyy,n,w[N],d[N],s[N],ans;
const double eps=1e-12;
int calc(){
	int res=0;
	if(xxx>yyy)swap(xxx,yyy);
	for(int i=1;i<=n;i++){
		if(s[xxx]-s[i]>=0)res+=w[i]*(s[xxx]-s[i]);
		else if(s[yyy]-s[i]>=0)res+=w[i]*(s[yyy]-s[i]);
		else res+=w[i]*(s[n+1]-s[i]);
	}
	return res;
}
void sa(){
	for(double t=1145;t>eps;t*=0.998){
		//printf("%d\n",ans);
		int x=xxx,y=yyy;
		xxx=rand()%n+1;yyy=rand()%n+1;
		if(xxx>yyy)swap(xxx,yyy);
		int now=calc(),del=now-ans;
		if(del<eps)ans=now;
		else if(exp(-del/t)*RAND_MAX<rand())xxx=x,yyy=y;
	}
} 
signed main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld%lld",&w[i],&d[i]);
		s[i]=s[i-1]+d[i-1];
	}
	s[n+1]=s[n]+d[n];
	xxx=1,yyy=2;
	ans=calc();
	while((double)clock()/CLOCKS_PER_SEC<=0.67)sa();
	printf("%lld",ans);
	return 0;
}

2022/7/21 16:31
加载中...