題意：?
? ? ? 有一個二維坐標(biāo)，y>0是海，y<=0是陸地，然后只能在y=0的岸邊上放雷達(dá)，有n個城市需要被監(jiān)控，問最少放多少個雷達(dá)。


思路：

? ? ? 貪心去做就行了，其實題目不難但是這個題目過的并不怎么順利，哎！，一開始我的想法是按照x排序，然后從左往右一個一個放置雷達(dá)，第一個放在第一個點相切的右側(cè)，....結(jié)果果斷wa了，然后就又想到可以求出每個城市的可放置區(qū)間，然后去貪心，還是wa了，原因是排序的時候還是按照x從小到大排序的，后來看了討論區(qū)一眼，才把排序是按照左區(qū)間排序的，一開始隱約考慮過這個，但是感覺按照x排沒有錯（一開始的想法），還有就是這個題目的數(shù)據(jù)比較坑人，要考慮d是負(fù)數(shù)或者y是負(fù)數(shù)的情況，如果全面的想，d是負(fù)數(shù)的話，如果所有的y都<=0那么輸出0，否則就輸出-1，如果y有大于0的，同時最大的y比b大，那么就輸出-1，然后就是正常貪心，貪心的時候遇到y(tǒng)<0的點直接跳過去不考慮，有點小坑啊，不過是一個不錯的簡單題。

#include<math.h> #include<stdio.h> #include<string.h> #include<algorithm>#define N 1000 + 10using namespace std;typedef struct {double l ,r;int id; }REG;REG reg[N]; int mark[N];bool camp(REG a ,REG b) {return a.l < b.l; }double minn(double x ,double y) {return x < y ? x : y; }double maxx(double x ,double y) {return x > y ? x : y; }int main () {int n ,l ,i ,d ,x ,y ,cas = 1;while(~scanf("%d %d" ,&n ,&d) && n + d){int jude1 = 0 ,jude2 = 0;memset(mark ,0 ,sizeof(mark));for(i = 1 ;i <= n ;i ++){scanf("%d %d" ,&x ,&y);if(y > 0) jude1 = 1;if(y > d) jude2 = 1;reg[i].l = x - sqrt(d * d * 1.0 - y * y * 1.0);reg[i].r = x + sqrt(d * d * 1.0 - y * y * 1.0);reg[i].id = i;if(y <= 0) mark[i] = 1;}printf("Case %d: " ,cas ++);if(!jude1){printf("0\n");continue;}if(jude2){printf("-1\n");continue;}double nowxl ,nowxr;int ansSum = 0;sort(reg + 1 ,reg + n + 1 ,camp);for(i = 1 ;i <= n; ++i){if(mark[reg[i].id]) continue;if(i == 1 || reg[i].l > nowxr){ansSum ++;nowxl = reg[i].l;nowxr = reg[i].r;}else{nowxl = maxx(nowxl ,reg[i].l);nowxr = minn(nowxr ,reg[i].r);}}printf("%d\n" ,ansSum);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的POJ1328贪心放雷达的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。