1.概述
原题的意思是,给定两个整型数字n(1<=n<=1000)和一个d(表示雷达的识别距离)。然后接下来的n行分别有两个数x,y表示岛I(i)的坐标(x,y)其中个i(1<=i<=n),你的目标是求可以覆盖所有岛屿的最少的雷达数量(雷达只能放在x轴上)。
2.我的想法
首先利用一个结构体point, 其中每一个x,y,mixx和maxx分别表示横坐标,纵坐标,以d为半径的且以圆心在x轴的雷达的位置的最小值以及最大值。
然后可以通过排序points(比较minx的位置确定循环的开始的位置)。
然后分别讨论几种情况:
设right表示第一次放雷达的位置(最左端的岛屿,为了能够最大覆盖,需要从maxx开始放置)。
假设下一个岛屿的索引是i+1(起始位置从i+1开始):
- 如果points[i+1].mixx > right 很显然I(i+1)是放置在right雷达覆盖不了的,所以需要增加雷达的数量,同时把雷达放在points[i+1].maxx上,(图1-1)。
- 很显然,如果points[i+1] <=tight 那么right位置的雷达是可以覆盖的,那我不管他(图1-1)。
- 如果points[i+1].mixx <=right 且points[i+1].maxx < right。也就是图1-2的情况,算法只要将雷达重新放在points[i+1].maxx上。就okay。
3.附上代码(但是无法AC。郁闷)
#include "stdio.h" #include "stdlib.h" #include <cmath> #define N 1001 #include <algorithm> struct point { int x; int y; int minx; int maxx; }; point points[N]; //POJ 1328 //贪心算法 我认为是可以的 但是还是不行 奇怪了 int res[N]; int np, d; bool cmp(const point &l, const point &p) { return l.minx < p.minx; } bool set_min_xpoint(point *dest) { int mm, mmmax; bool flag = false; if (dest->y > d) { flag = true; } else { int sr = sqrt(d*d-dest->y *dest->y); dest->minx = dest->x- sr; dest->maxx = dest->x+ sr; flag = false; } return flag == false; } int main() { int pos = 0; while (~scanf("%d %d", &np, &d) && (np != 0 && d != 0)) { bool res1 = true; for (int i = 0; i<np; ++i) { scanf("%d %d", &points[i].x, &points[i].y); if (!set_min_xpoint(&points[i])) { res1 = false; continue; } //printf("---%d %d\n", points[i].minx, points[i].maxx); } if (res1 == false) { printf("Case %d: %d\n", ++pos, -1); continue; } std::sort(points, points + np, cmp); /* int sum = 1; for (int i = 0; i < np - 1; ++i) { if (points[i + 1].minx >= points[i].minx && points[i + 1].minx <= points[i].maxx) { --sum; } } */ //选取之前放置雷达的位置 然后查找下一个的左端点是否在当前的右边界的:1.右边:那么在当前位置的右边放下雷达 //2.左边:那么肯定是可以覆盖的 //如果下一个的位置的右边界在之前放置雷达的位置左边 那么就要在这个的最大位置放置雷达 那么之前的都可以覆盖了 //如果在右边也在覆盖范围内 int sum = 1; int right = points[0].maxx; for (int i = 0; i < np - 1; ++i) { if (points[i + 1].minx > right) { ++sum; right = points[i + 1].maxx; } else if(points[i+1].maxx < right) { right = points[i + 1].maxx; } } //*/ printf("Case %d: %d\n", ++pos, sum); } return 0; }