题意简述

如图所示，x轴上方有n（1≤n≤1000）个岛屿（坐标均为整数）， 在x轴上可以放置覆盖半径为d（整数）的雷达。问最少放置多少个雷达能够覆盖所有岛屿？如果无法全部覆盖则输出-1。

算法分析

这道题折磨了我好几天，一直WA一直WA…本来觉得没多难都被WA崩溃了…好了不扯了进正题。

首先分析无解的情况。容易得到：当且仅当某一岛屿的纵坐标大于雷达半径时，此组数据无解。 这个可以在读入时直接判断。需要注意的是，即便已经得到无解结论，也应等所有数据输入完毕再输出-1。

接下来就是求解过程了。

这题用贪心。但刚拿到手时，由于思考的局限性给出了错误的贪心策略。导致WA了好几次…（血泪史啊！T.T）下面先说错误的：

• 错误贪心策略：

1. 所有岛屿按照横坐标从小到大排序。若横坐标相等则按纵坐标从大到小排序。
2. 首先利用第一个岛屿坐标，选择能够覆盖住它的，在它右侧距离最远的x轴上的点，放下第一个雷达。（位置可由勾股确定）。如图所示：橘色为雷达位置。
3. 扫描下一个点，如果在当前雷达覆盖范围内则继续向后扫描，否则以该点坐标为基准，依照步骤2中方法确立一个新雷达位置。直到所有岛屿被覆盖。

这个贪心策略至少我当时完全没有想到任何破绽…可是一直WA一直WA…直到学长给了这样一组数据：

其中雷达半径为5。这组数据只需在（1,0）放置一个雷达即可。但按照上面的策略，则需放置两个雷达。分别在（1,0）和（3,0）。

这让我相当郁闷……最后无奈上网找了其他人的AC程序，才找到正确的贪心策略。

• 正确贪心策略：

1. 首先在读入时，用勾股算出x轴上能够覆盖住当前点的区间。
2. 将区间按照左端点排序。
3. 因为若两区间有包含关系，则小区间内存在雷达即可满足大区间需求。所以从右向左扫描所有区间，标记因包含关系无需处理的大区间。
4. 从左向右扫描。首先判断该区间是否被标记。若区间需要处理，则判断当前雷达是否在区间内。若在则继续向下扫描。若不在，则选取区间右端点标记为新雷达位置。同时累加器自增。扫描结束后输出累加器值即可。

Problem Status: AC。时间0ms，内存392k

——————————————————————分割线——————————————————————

TIPS:

在思考这个正确的贪心策略时，发现网上的那个AC程序是这样实现去除包含关系的：

for(i=0;i

b[i]是标记数组，pos表示当前雷达位置。area[i]是存储区间的数组。其中[0]存左端点，[1]存右端点。

这种方法其实有一个漏洞：无法去除两个左端点相同的区间的包含关系。例如：区间[1,2]和[1,3]无论其先后顺序，都不会被标记为存在包含的区间。

但如果继续考虑下面判断是否新建雷达的算法，则可以容易发现这个并不妨碍统计雷达个数。

可参照下面的程序样例进行理解。

——————————————————————分割线——————————————————————

为进行比对，下面将贴出错误贪心策略的代码及正确贪心策略的代码。

程序样例

• 错误贪心策略：

#include
#include
#include

int comp(const void *a, const void *b)
{
    int *c,*d;
    c=(int *)a; d=(int *)b;
    if (*c>*d) return 1;
    if (*c<*d) return -1;
    c++; d++;
    if ((*c)<(*d)) return 1;
    return -1;
}

double dis(double pos, int x, int y)
{
    double a,b,c;
    a=y*y;
    b=(x-pos)*(x-pos);
    return sqrt(a+b);
}

int main()
{
    int n,d,i,p[1000][2],ans=1,c=0,b[1000]={1};
    double pos;
    scanf("%d%d",&n,&d);
    while(!(n==0&&d==0))
    {
        c++;
        if (n==0)
        {
            printf("Case %d: 0n",c);
            scanf("%d%d",&n,&d);
            continue;
        }
        ans=1;
        for(i=0;id) ans=-1;
        }
        if (ans==-1||d==0)
        {
            printf("Case %d: -1n",c);
            scanf("%d%d",&n,&d);
            continue;
        }
        comp(p[0], p[1]);
        qsort(p,n,2*sizeof(int),comp);
        pos=p[0][0]+sqrt(d*d-p[0][1]*p[0][1]);
        for(i=1;i<=d*1.0)
                continue;
            else
            {
                ans++;
                pos=p[i][0]+sqrt(d*d-p[i][1]*p[i][1]);
            }
        printf("Case %d: %dn",c,ans);
        scanf("%d%d",&n,&d);
    }
    return 0;
}

• 正确贪心策略：

#include
#include
#include
int comp(const void *a, const void *b)
{
    double *c, *d;
    c=(double *)a; d=(double *)b;
    if (*c>*d) return 1;
    return -1;
}
int main()
{
    int n,d,c=0,p[1000][2],i,ans,b[1000]={0};
    double pos,area[1000][2],t;
    scanf("%d%d",&n,&d);
    while(!(n==0&&d==0))
    {
        c++;
        ans=0;
        for(i=0;id) ans=-1;
            else
            {
                 area[i][0]=sqrt(d*d-p[i][1]*p[i][1]);
                 area[i][1]=p[i][0]+area[i][0];
                 area[i][0]=p[i][0]-area[i][0];
            }
            b[i]=0;
        }
        if (ans==-1||d==0)
        {
            printf("Case %d: -1n",c);
            scanf("%d%d",&n,&d);
            continue;
        }
        qsort(area,n,2*sizeof(double),comp);
        t=area[n-1][1];
        for(i=n-2;i>=0;i--)
            if (area[i][1]>=t) b[i]=1; else t=area[i][1];
        pos=-2100000000;
        for(i=0;i