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

· · 题解

题目大意

暴力枚举显然不行。又没有其他的做法，因此使用模拟退火算法。

模拟退火算法的流程大致就是：选取一个解作为初始解并设定一个初始温度，然后根据温度高底控制波动范围，在波动范围内随即生成新的解并计算能量差，如果这个解更优那么当然选择接受，否则以e^{\frac{ΔE}{T}}的概率接受这个解，每次生成新解之后把温度降低一点。因此模拟退火中找到的解随着温度降低稳定下来，最终有很大概率找到最优解，并且比较快就能运行完。

如果还不清楚的话先去做一下P1337。

结构如下。

void SA()
{
    double t=3000;
    while(t>=0.00000000001)
    {
        int now=随机生成的新解
        int d=新解能量-找到的最优解的能量
        if(d比当前最优解更优)ans=now;
        else if(exp(-d/t)*RAND_MAX>rand())
            ans=now;
        t*=0.995;
    }
}

同时，模拟退火一遍有可能得到的不是最优的，所以一般要多跑几遍模拟退火增加正确率。

然后看这题。

定义

首先，这题要存储每个建筑的位置和敌人的位置，因此我们可以使用两个结构体数组，分别存储x坐标、y坐标和半径。敌人可以视为半径为0的园。

定义数组building为建筑的数组，di是敌人的数组。

struct node{
    int x,y,r;//x坐标、y坐标以及半径
}building[15],di[10005];//building是建筑，di是敌人
int n,m,r,xs,ys,ans;//xs,ys是初始解和每次生成的新解的坐标

计算炸死的敌人

要在满足半径不大于r并且不炸到建筑的情况下，求出这个位置的解最多能炸死几个人。

显然满足条件的情况下，半径越大就越优，所以此时半径取r和到每个建筑边缘的距离之间的最小值。到建筑的距离就是到建筑的圆心的距离减去建筑的半径。

至于计算距离，可以看成以两个点(x_1,y_1)和(x_2,y_2)为两个锐角顶点、两条直角边分别平行于x轴和y轴的直角三角形的斜边边长。

因此(x_1,y_1)和(x_2,y_2)的距离为\sqrt{(x_2-x_1)^2+(y_2-y_1)^2}

不理解？建立平面直角坐标系，自己画画看。

//里面的jljs函数求出两点间的距离，这里不放了
int js(double x,double y)//计算最多能炸到几个
{
    int i,ans=0;
    double jl=r;//因为炸弹半径最多r，所以从r开始，每次计算到每个建筑边缘的距离并选取更小的一个
    for(int i=1;i<=n;i++)//计算出最大的半径，等于到每个建筑边缘的最小值
    {
        double jlt=jljs(building[i].x,building[i].y,x,y)-building[i].r;//到塔的距离减去塔的半径
        if(jlt<0)return 0;//炸弹不能扔在塔上
        if(jl>jlt)jl=jlt;//找到最大的不炸到塔的半径
    }
    for(int i=1;i<=m;i++)//计算能炸到几个
        if(jljs(di[i].x,di[i].y,x,y)<=jl)//如果到敌人的距离小于求出的最大半径
            ans++;//那么可以炸死
    return ans;
}

模拟退火过程

直接套上模板即可。

在主函数中，先预处理出在每个敌人的中间的位置，然后从这个位置开始模拟退火，多跑几遍。

调用入口：

//多跑几遍
void solve(){
    sa();sa();sa();
    sa();sa();sa();
}

//主函数中
    solve();

最后是AC代码。

#include<bits/stdc++.h>
using namespace std;

//用结构体存储
struct node
{
    int x,y,r;//坐标、半径
}building[15],di[10005];//分别存储塔和敌人
int n,m,r,xs,ys,ans;

//计算两点之间距离
double p(double x)//计算平方
{
    return x*x;
}
double jljs(double x,double y,double a,double b)//计算距离
{
    return sqrt(p(x-a)+p(y-b));//把横坐标之差和纵坐标之差分别看作两条直角边
}

//计算能炸到几个人
int js(double x,double y)//计算最多能炸到几个
{
    int i,ans=0;
    double jl=r;
    for(int i=1;i<=n;i++)
    {
        double jlt=jljs(building[i].x,building[i].y,x,y)-building[i].r;//到建筑的距离减去建筑的半径
        if(jlt<0)return 0;//炸弹不能扔在建筑上
        if(jl>jlt)jl=jlt;//找到最大的不炸到建筑的半径
    }
    for(int i=1;i<=m;i++)
        if(jljs(di[i].x,di[i].y,x,y)<=jl)//计数
            ans++;
    return ans;
}

//模拟退火过程
void sa()
{
    double ansx=xs,ansy=ys,nowx,nowy,t=3000;
    while(t>=0.0000000001)
    {
        nowx=xs+((rand()<<1)-RAND_MAX)*t;//随机生成新x坐标
        nowy=ys+((rand()<<1)-RAND_MAX)*t;//随即生成新y坐标
        double now=js(nowx,nowy),d=ans-now;//计算能量差
        if(d<0)//如果更优
            xs=ansx=nowx,ys=ansy=nowy,ans=now;//更新最优解
        if(exp(-d/t)<rand())//否则一定概率接受
            ansx=nowx,ansy=nowy;
        t*=0.995;//降温
    }
}

//多跑几遍
void solve(){
    sa();sa();sa();
    sa();sa();sa();
}

int main(){
    srand(time(0));
    cin>>n>>m>>r;
    for(int i=1;i<=n;i++)
        cin>>building[i].x>>building[i].y>>building[i].r;
    for(int i=1;i<=m;++i)
    {
        cin>>di[i].x>>di[i].y;
        xs+=di[i].x;ys+=di[i].y;
    }
    xs/=m;ys/=m;//从敌人中间开始炸
    solve();
    cout<<ans;
    return 0;
}