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;
}