Dayi Lin, Ph.D.

Principal Researcher, AI & Software Engineering

POJ-1328 解题报告

POJ

题意简述

如图所示,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 < n; i++)
  if (b[i] == 0)
    if (pos < area[i][0]) {
      ans++;
      pos = area[i][1];
    }

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

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

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

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

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

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

程序样例

错误贪心策略:

#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: 0\n", 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: -1\n", 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: %d\n", c, ans);
    scanf("%d%d", &n, &d);
  }
  return 0;
}

正确贪心策略:

#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: -1\n", 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: %d\n", c, ans);
    scanf("%d%d", & n, & d);
  }
  return 0;
}

Leave a Reply

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