题解 P1158 【导弹拦截】

· · 题解

马上要CSP了，赶快来做点真题

做到了这个题。然后，我太蕉♂急了，第一反应：对于每个点，去找最近的系统管。

刷刷写出代码，信心满满的交上去，完美的只有40分。去看了一下讨论，讨论区里有一个和我一样只有40分的。和我的做法一样。

然后我来讲一下这个算法为什么不对，顺便提醒一下大家，在做CSP/NOIP的贪心题时，一定要van♂分小心。

是这样的：有一些点，如果每个就近选，就会用更多的系统，导致答案分散，用大量的花费完成少量的任务。更优的解法是，一个系统虽然花费的更多，但是一次珂以管理更多导弹。

这句话有点难懂，但是看图就明白了。

图中，A,B是拦截系统，C,D是两个导弹。

然后按照刚刚的“就近原则”，应该是A管理C，B管理D。但是这样的花费是20+37=57。

实际上，只要B管理D就足够了。这样的花费是37。

这种算法失败的原因，就是因为把原本一个系统就能解决的事情，交给了两个系统。

那么正确的算法又是什么呢。

首先，导弹显然是无序的，根据常年经验和数据我们意识到要排序。

然后我们意识到，我们要把这些导弹分成两个部分，不一定非空，一部分给A管，部分给B管。

然后我们灵机一动，我们按照到A的距离排序，然后一个前缀给A，除此之外的部分（一个后缀）给B。

然后枚举断点找最小即珂。

代码：

#include <bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet
{
    #define N 155555
    #define F(i,l,r) for(int i=l;i<=r;++i)
    #define D(i,r,l) for(int i=r;i>=l;--i)
    #define Fs(i,l,r,c) for(int i=l;i<=r;c)
    #define Ds(i,r,l,c) for(int i=r;i>=l;c)
    #define Tra(i,u) for(int i=G.Start(u),__v=G.To(i);~i;i=G.Next(i),__v=G.To(i))
    #define MEM(x,a) memset(x,a,sizeof(x))
    #define FK(x) MEM(x,0)

    struct node{int x,y;}a[N];
    int n;
    void R1(int &x)
    {
        x=0;char c=getchar();int f=1;
        while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar();
        while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
        x=(f==1)?x:-x;
    }
    void Input()
    {
        R1(a[1].x),R1(a[1].y),R1(a[2].x),R1(a[2].y);
        R1(n);
        F(i,3,n+2) R1(a[i].x),R1(a[i].y);
    }

    int dis2(node a,node b)
    {
        return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
    }
    bool cmp(node x,node y)
    {
        return dis2(x,a[1])<dis2(y,a[1]);
    }
    int dis[N];
    void Soviet()
    {
        sort(a+3,a+n+3,cmp);
        D(i,n+2,3)
        {
            dis[i]=max(dis[i+1],dis2(a[i],a[2]));
        }

        int ans=0x7f7f7f7f;
        F(i,3,n+2)
        {
            int r1=dis2(a[i],a[1]);
            int r2=dis[i+1];
            ans=min(ans,r1+r2);
        }
        printf("%d\n",ans);
    }

    #define Flan void
    Flan IsMyWife()
    {
        Input();
        Soviet();
    }
}
int main()
{
    Flandre_Scarlet::IsMyWife();
    getchar();getchar();
    return 0;
}