题解 P1433 【吃奶酪】

· · 题解

1 模拟退火

这个不用多说了吧，就是基本套路。

一个初始温度，一个终止温度，一个降温速率。

每次交换两个点的位置，如果比当前最优解优就替换，否则以概率接受。

当然只能拿到 80~90 pts 的成绩（当然有可能是我的 rp 差）。

没啥意思。

2 随机贪心

有个贪心方法是从 (0,0) 点开始，每次找最近的点是吧？

但是这个很容易找出反例。

所以可以每次把到所有没有取过的点的距离排序，然后取一个点。

最容易想的就是随机取一个，即 rand\bmod n（下标从 0 开始，rand 表示一个 0\sim \inf 之间均匀分布的随机数），但是这样距离较近的点就没有优势了。

我现在想出来的是 rand\bmod (rand\bmod n+1)，在所有的返回值中，0 有 n 个，1 有 n-1 个……

这个函数还不错。

拿到的分数非常不稳定，但是还是有可能 AC 的。

#include<bits/stdc++.h>
using namespace std;
int n;
double mn=1e9;
double x[16],y[16];
int p[16];
const int c=100;
const double o=0.9999,e=1e-16;
double ask()
{
    double s=0,px=0,py=0;
    bool t[16]={0};
    pair<double,int> jl[16],ans;
    int i,j,wz,w;
    for(i=0;i<n;i++)
    {
        wz=0;
        for(j=1;j<=n;j++)
            if(!t[j])
                jl[wz++]=make_pair((px-x[p[j]])*(px-x[p[j]])+(py-y[p[j]])*(py-y[p[j]]),j);
        sort(jl,jl+wz);
        ans=jl[rand()%(rand()%wz+1)];
        w=ans.second;
        s+=sqrt(ans.first),t[w]=1;
        px=x[p[w]],py=y[p[w]];
    }
    return s;
}
void RG()
{
    random_shuffle(p+1,p+1+n);
    mn=min(mn,ask());
}
int main()
{
    srand(time(0));
    int i;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>x[i]>>y[i];
        p[i]=i;
    }
    while(clock()<CLOCKS_PER_SEC*0.93)
        RG();
    printf("%.2f",mn);
}

3 模拟退火&随机贪心

把模拟退火的估价函数换成随机贪心的函数。

没了。

实测拿到的分数比随机贪心高。

#include<bits/stdc++.h>
using namespace std;
int n;
double mn;
double x[16],y[16];
int p[16];
const double o=0.9999,e=1e-16;
double ask()
{
    double s=0,px=0,py=0;
    bool t[16]={0};
    pair<double,int> jl[16],ans;
    int i,j,wz,w;
    for(i=0;i<n;i++)
    {
        wz=0;
        for(j=1;j<=n;j++)
            if(!t[j])
                jl[wz++]=make_pair((px-x[p[j]])*(px-x[p[j]])+(py-y[p[j]])*(py-y[p[j]]),j);
        sort(jl,jl+wz);
        ans=jl[rand()%(rand()%wz+1)];
        w=ans.second;
        s+=sqrt(ans.first),t[w]=1;
        px=x[p[w]],py=y[p[w]];
    }
    return s;
}
void SA()
{
    double s=1,ans;
    int w1,w2;
    for(;s>e;s*=o)
    {
        w1=rand()%n+1,w2=rand()%n+1;
        swap(p[w1],p[w2]);
        ans=ask();
        if(ans<mn)
            mn=ans;
        else if(exp((mn-ans)/s)*RAND_MAX<rand())
            swap(p[w1],p[w2]);
        if(clock()>CLOCKS_PER_SEC*0.97) break;
    }
}
int main()
{
    srand(time(0));
    int i;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>x[i]>>y[i];
        p[i]=i;
    }
    mn=ask();
    while(clock()<CLOCKS_PER_SEC*0.97)
        SA();
    printf("%.2f",mn);
}

因为运行中上面的 SA 运行时间较长，所以我设定了一个

if(clock()>CLOCKS_PER_SEC*0.97) break;

可以保证不 TLE。