社区讨论
为什么TLE了?
P1433吃奶酪参与者 2已保存回复 5
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 5 条
- 当前快照
- 1 份
- 快照标识符
- @mhj13sp6
- 此快照首次捕获于
- 2025/11/03 19:00 4 个月前
- 此快照最后确认于
- 2025/11/03 19:00 4 个月前
90pts,有一个点TLE了。
但是我卡时了,按理说很难TLE。
CPP#include<bits/stdc++.h>
using namespace std;
#define db double
#define N 20
struct node{db x,y;} z[N];
int n;
db ansx,ansy;
db ans=1e9;
db delta=0.997;
const int start=10000;
const db small=1e-4;
db dis(db x1,db y1,db x2,db y2)
{
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
db getsum()
{
db sum=dis(0.0,0.0,z[1].x,z[1].y);
for(int i=2;i<=n;i++) sum+=dis(z[i-1].x,z[i-1].y,z[i].x,z[i].y);
return sum;
}
void simulate_anneal()
{
db t=start,cnt=getsum();
ans=min(ans,cnt);
while(t>small)
{
int l=rand()%n+1,r=rand()%n+1;
if(l==r) continue;
swap(z[l],z[r]);
db now=getsum();
db shu=now-cnt;
if(shu<0)
{
cnt=now;
ans=min(ans,now);
}
else if(exp(-shu/t)*RAND_MAX*1.0>rand()) cnt=now;
else swap(z[l],z[r]);
t=t*delta;
}
}
int start_time=clock();
void solve()
{
while(clock()-start_time<0.9*CLOCKS_PER_SEC)
simulate_anneal();
}
int main()
{
srand(time(0)),srand(rand()^clock());
cin>>n;
for(int i=1;i<=n;i++)
cin>>z[i].x>>z[i].y;
solve();
printf("%.2f\n",ans);
}
回复
共 5 条回复,欢迎继续交流。
正在加载回复...