关于在luogu卡时间
  • 板块学术版
  • 楼主halehu
  • 当前回复6
  • 已保存回复6
  • 发布时间2024/10/11 12:34
  • 上次更新2024/10/11 16:53:36
查看原帖
关于在luogu卡时间
365777
halehu楼主2024/10/11 12:34

rt,当我用计时器卡模拟退火的时间时(比如超过900ms我就退出)洛谷每次跑出来的记录却显示只运行了几ms,这是怎么回事?

另外,noip评测机上计时器能生效吗?

以P7962为例子:(由于完全隐私保护,提交记录就补贴了)

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e4 + 5;
int n,a[N],b[N],tmp[N],st,ed,ans;
bool cmp(int x,int y){
	return x > y;
}
int random(int l,int r){
	return l + rand() % (r - l + 1);
}
bool check(int x,int y){
	int flag = 0;
	for(int i=2;i<n;i++){
		if(flag && b[i] > b[i+1]) return 0;
		if(b[i] < b[i+1]) flag = 1;
	}
	return 1;
}
int cal(){
	int sum1 = 0,sum2 = 0;
	for(int i=1;i<=n;i++){
		tmp[i] = tmp[i-1] + b[i];
		sum1 += tmp[i],sum2 += tmp[i] * tmp[i];
	}
	return sum2 * n - sum1 * sum1;
}
void SA(){
	int last,now; ans = last = cal();
	for(double t=1e3;t>=1e-4;t*=0.95){
		ed = clock(); if(ed - st > 900) return; //此处计时器根本没用 
		int x = random(2,n-1),y = random(x,n);
		swap(b[x],b[y]);
		if(!check(x,y)){
			swap(b[x],b[y]);
			continue;
		}
		now = cal(); ans = min(ans,now);
		if(exp((last - now) / t) > (double)rand() / RAND_MAX) last = now;
		else swap(b[x],b[y]);
	}
}
signed main(){
	srand(unsigned(time(0)));
	st = 0.0,ed = 0.0;
	scanf("%lld",&n);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]),b[i] = a[i] - a[i-1];
	sort(b+2,b+n/2+1,cmp),sort(b+n/2+1,b+n+1);
	st = clock();
	while(ed - st < 900) SA(); //此处计时器根本没用 
	printf("%lld\n",ans);
	return 0;
}
2024/10/11 12:34
加载中...