题解 P5544 【[JSOI2016]炸弹攻击1】

· · 题解

upd: 经过多次修改退火的参数，AC率几乎能达到100%

前言：

昨天刚刚学了模拟退火，就拿这道题试了一下手 ，正好看见没有人发题解，就自己写了一篇

题意如下：

地图上有两种单位，建筑和敌人，建筑占据面积为半径不定的圆形，敌人为一个点，你可以在地图上任意一点放置一个半径不超过R（已给出）的炸弹，求在不炸到建筑的情况下，能覆盖的敌人数目最大值

分析：

题目要求在平面内任选一点，第一时间就想到了可以用模拟退火一类的随机化算法，任意枚举平面内一些点，进行退火时求出在满足不炸到建筑时炸弹的最大范围，求出范围内覆盖敌人的数目，进行更新

tips:

  1. 题目给的数据为int型整数，但进行欧式距离的计算时，要表示为double型，也就是说存在强制类型转换，容易造成数据溢出

  2. 本题的数据范围比较大，退火的参数选择需要不断尝试 ，手算一下T的上下界，当T过大过小时都难以找到更优解，这样减小了T的范围，剩下时间可以多SA几次

  3. 将改动坐标时的rand对一个合适大小的数取模,这样可以防止随机的移动过于不稳定

提交记录

我因为各种原因（强制类型转换写错，参数调不对，退火条件写错)交了好几次才A掉

模拟退火关键

先前的题解错误的把模拟退火写成了爬山算法，可能因为数据的原因A掉了，但是正确的模拟退火在判断是否接受是exp函数里的值是负的，乘RANDMAX时肯定会不接受，所以为了解决这个问题，有如下的方法

我们还可以在遇到次优解判断是否接受时除以根号T，因为T的变化较大，这样确保在T较小时也有可能更新，T较大时也不会全盘接受。

bool judge(int delta,double tep)//tep表示温度
    {
        return ( exp(delta/sqrt(tep)) > rand() );
    }

话不多说上代码


#include<bits/stdc++.h>

using namespace std;

namespace zzc
{
    const double dec = 0.995;//降温系数 
    const double esp = 1e-10;
    int n,m,r,ans=0;
    double sumx,sumy; 

    struct build
    {
        int x,y,r;
    } b[15];

    struct human
    {
        int x,y;
    } h[1005];

    double calc(double x1,double y1,double x2,double y2)//计算欧氏距离 
    {
         return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
    }

    int check(double x,double y)//计算范围内覆盖敌人数目 
    {
        int sum=0;
        double dis,R=(double)r;
        for(int i=1;i<=n;i++)
        {
            dis=calc(x,y,b[i].x,b[i].y);
            dis-=(double)b[i].r;
            R=min(R,dis);
        }

        for(int i=1;i<=m;i++)
        {
            dis=calc(x,y,h[i].x,h[i].y);
            if(dis<=R) sum++;
        }
        return sum;
    }

    //原先的题解错写成了爬山算法
    //这里我做了一点修改  
    bool judge(int delta,double tep)
    {
        return ( exp(delta/sqrt(tep)) > rand() );
    }

    void solve()
    {
        double tep=1000;//初温 
        int tot=0;
        while(tep>esp)
        {
            double sx=( rand()*2- RAND_MAX)*tep;//随机化移动距离，随着温度降低移动更稳定 
            double sy=( rand()*2- RAND_MAX)*tep;
            int sum=check( sumx+sx ,sumy+sy );
            int delta=sum-tot;
            if(delta>0)//delta大于0表示新的解更优 
            {
                sumx+=sx;
                sumy+=sy;
                tot=sum;
                ans=max(ans,tot);
            }
            else if(judge(delta,tep))
            {
                sumx+=sx;
                sumy+=sy;
                tot=sum;
            }
            tep*=dec;
        }
    }

    void init()
    {
        sumx=0;sumy=0;
        scanf("%d%d%d",&n,&m,&r);
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d%d",&b[i].x,&b[i].y,&b[i].r);
        }
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&h[i].x,&h[i].y);
            sumx+=h[i].x;
            sumy+=h[i].y;
        }
        sumx/=m;
        sumy/=m;
    }

    void work()
    {
        srand((int)time(0));
        init();
        for(int i=1;i<=6;i++) solve();
        printf("%d\n",ans);
    }

}

int main()
{
    zzc::work();
    return 0;
}

如果有问题欢迎大家私信或者评论，我尽量都去看