社区讨论

为什么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 条回复,欢迎继续交流。

正在加载回复...