贪心思路:
cor[i]数组保存覆盖到该岛的雷达能放置的区间,然后按照左端点从小到大对数组排序。
只要雷达放置在某岛的cor[i]保存的区间内,这个岛就能被这个雷达覆盖。
排序后,相邻的两个区间只有三种情况。
1.第二个区间完全在第一个区间的后面。
2.第一个区间的后边一部分与第二个区间的前边一部分重合。
3.第二个区间包含在第一个区间内。
先把第一个雷达放在第一个区间的右端点。
1.如果第二个区间与第一个区间属于相邻区间的第一种情况,那么第一个区间的右端点显然不在第二个区间内,需要在第二个区间的右端点放一个新的雷达。
2.如果第二个区间与第一个区间属于第二种情况,那么第一个区间的右端点在第二个区间之内,因此第二个岛能被这个雷达覆盖,不需要新雷达。
3.如果属于第三种情况,第一个区间的右端点不在第二个区间内,但是第二个区间的右端点在第一个区间之内,所以把雷达放在第二个区间的右端点,不需要新雷达。
第二个区间处理完毕后,以新的雷达(或不需要新雷达就用原来的雷达)作为标准来处理第三个区间。
然后依次处理第四个第五个,直到处理完毕。
如果某个岛的y坐标大于d,这个岛就无法被雷达覆盖,输出-1。
Source Code
Problem: 1328 | User: yueashuxia | |
Memory: 696K | Time: 16MS | |
Language: G++ | Result: Accepted |
#include<stdio.h> #include<string.h> #include<math.h> #include<iostream> #include<algorithm> using namespace std; struct node { float l, r; }cor[1005]; bool cmp(node a, node b) { return a.l < b.l; } int main(){ int i, res, NO = 1, N; float d, D, x, y, r; bool flag; while(scanf("%d%f", &N, &D), N||D) { for(i = flag = 0; i < N; i ++) { scanf("%f%f", &x, &y); if(y > D) flag = 1; if(flag == 0) { d = sqrt(D*D - y*y); cor[i].l = x - d; cor[i].r = x + d; } } if(flag) {printf("Case %d: -1\n", NO++); continue;} sort(cor, cor+N, cmp); res = 1; r = cor[0].r; for(i = 1; i < N; i ++) { if(cor[i].l > r) { res++; r = cor[i].r; } else if(cor[i].r < r) { r = cor[i].r; } } printf("Case %d: %d\n", NO++, res); } //system("pause"); return 0; }