【贪心】POJ 1328：Radar Installation

一、题目内容

POJ 1328 原题地址

二、题意解释

假设海岸线是一条无限延伸的直线。陆地在海岸线的一侧，而海洋在另一侧。每一个小的岛屿是海洋上的一个点。 雷达坐落于海岸线上，只能覆盖d距离，所以如果小岛能够被覆盖到的话，它们之间的距离最多为d。 题目要求计算出能够覆盖给出的所有岛屿的最少雷达数目。

三、代码及注释

#include<iostream> #include<math.h> #include<algorithm> #define INF 0x7ffffff using namespace std; //思路，可转换成 “安排节目”问题 const int Max = 1005; struct { int x, y; } isl[Max]; // 小岛的数据。 struct data { float sta, end; } rad[Max]; // 小岛所对应雷达的数据。 bool cmp(data a, data b) { if(a.end < b.end) return true; else return false; } int main() { int n, d, t = 1; while(cin >> n >> d && n != 0) { int i, j, max_y = 0;//max_y用来记录岛屿的最大y值，如果这个值大于d，那么说明不能覆盖全，不成立 for(i = 0; i < n; i ++) { cin >> isl[i].x >> isl[i].y; if(isl[i].y > max_y) max_y = isl[i].y; } getchar(); getchar(); // PE了两次。 cout << "Case " << t ++ << ": "; if(max_y > d || d < 0) { cout << -1 << endl; continue; } float len; for(i = 0; i < n; i ++) { // 求出小岛所对应雷达的可能覆盖范围。 len = sqrt(1.0 * d * d - isl[i].y * isl[i].y); rad[i].sta = isl[i].x - len; rad[i].end = isl[i].x + len; } //以下类似安排节目题目思想 sort(rad, rad + n, cmp); // 根据rad的end值进行排序。 int ans = 0; float pos=-INF; for(int i=0;i<n;i++){ if(pos<rad[i].sta){ pos=rad[i].end; ans++; } } cout << ans << endl; } return 0; }