POJ-1328 解题报告

题意简述

如图所示,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程序是这样实现去除包含关系的:
[c]
for(i=0;i<n;i++)
if (b[i]==0)
if (pos<area[i][0])
{
ans++;
pos=area[i][1];
}
[/c]
b[i]是标记数组,pos表示当前雷达位置。area[i]是存储区间的数组。其中[0]存左端点,[1]存右端点。

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

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

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

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

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

程序样例

  • 错误贪心策略:
  • [c]
    #include<stdio.h>
    #include<stdlib.h>
    #include<math.h>

    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;i<n;i++)
    {
    scanf("%d%d",&p[i][0],&p[i][1]);
    if (p[i][2]>d) 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<n;i++)
    if (dis(pos,p[i][0],p[i][1])<=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;
    }

    [/c]

  • 正确贪心策略:
  • [c]#include<stdio.h>
    #include<stdlib.h>
    #include<math.h>
    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;i<n;i++)
    {
    scanf("%d%d",&p[i][0],&p[i][1]);
    if (p[i][1]>d) 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<n;i++)
    if (b[i]==0)
    if (pos<area[i][0])
    {
    ans++;
    pos=area[i][1];
    }
    printf("Case %d: %dn",c,ans);
    scanf("%d%d",&n,&d);
    }
    return 0;
    }
    [/c]

Leave a Reply

Your email address will not be published. Required fields are marked *