模拟退火求调
查看原帖
模拟退火求调
1050021
likezheng2023楼主2024/5/17 20:24
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}return x*f;}
const int MAXN=1e6+10;
const double EPS=1e-7,DOWN=0.99995;
struct Node{
	int pos,id;
}node[MAXN];
int n,m,p,nowp,ans,ansl,ansr;
inline bool cmp(Node x,Node y){
	return x.pos<y.pos;
}
inline bool check(int l,int r){
	int t=m;
	if(node[nowp].pos<=r) t+=5;
	if((node[r].pos-node[l].pos)*2<=t) return true;
	else return false;
}
inline void SA(){
	double temp=5;
	while(temp>EPS){
		if((double)clock()/CLOCKS_PER_SEC<0.99) return;
		int l=ansl+temp*rand(),r=ansr+temp*rand();
		if(l>r) swap(l,r);
		l=max(l,1*1ll);
		r=min(r,n*1ll);
		while(node[l].pos>0) l--;
		while(node[r].pos<0) r++;
		if(check(l,r)){
			if(ans<r-l+1){
				ans=r-l+1;
				ansl=l;
				ansr=r;
			}else{
				int delta=ans-r+l-1;
				if (exp(-delta/temp)>rand()) ansl=l,ansr=r;
			}
			
		}
		temp*=DOWN;
	}
}
signed main(){
	srand(time(0));
	n=read(),m=read(),p=read();
	for(int i=1;i<=n;i++) node[i].pos=read(),node[i].id=i;
	sort(node+1,node+1+n,cmp);
	for(int i=1;i<=n;i++) if(node[i].id==p){
		nowp=i;
		break;
	}
	while((double)clock()/CLOCKS_PER_SEC<0.99) SA();
	cout<<ans<<'\n';
	return 0;
}
2024/5/17 20:24
加载中...