pku 1328 Radar Installation(貪心)

該題題意是為了求出能夠覆寫所有島嶼的最小雷達數目，每個小島對應x軸上的一個區間，在這個區間内的任何一個點放置雷達，則可以覆寫該小島，區間範圍的計算用[x-sqrt(d*d-y*y),x+sqrt(d*d-y*y)];

這樣，問題即轉化為已知一定數量的區間，求最小數量的點，使得每個區間内鬥至少存在一個點。

例如這組資料：

3 2

0 0

1 2

4 0

我們算出區間并按區間起始位置排序後有：[-2，2],[1，1],[2，6]三個區間。我們用一個變量currentRight記錄目前的最右的雷達（為了能夠照顧到後面的雷達，我們總是盡可能把雷達放置在右端），首先初始化currentRight=range[1].right;因為range[2].right<=currentRight，是以區間1包含區間2，這時候我們不給2增加雷達，而是把currentRight往左移至range[2].right，更新currentRight=1;對于區間3，因為currentRight=1<range[3].left,這時就要增加一個雷達數，然後更新currentRight=range[3].right。還有一種可能是range[i].left<=currentRight<=range[i].right。這時currentRight已經可以覆寫該區間，直接跳過。

有一點讓我比較郁悶的是，用qsort沒過，換成sort就過了。

#include "math.h"

#include <algorithm>

#include <iostream>

using namespace std;

struct node

{

double left,right;

}range[1001];

bool cmp(node a,node b)

{

return a.left<b.left;

}

int main()

{

int n,flag,cnt,k=0;

double currentRight,x,y,d;

while(scanf("%d%lf",&n,&d)&&!(n==0&&d==0))

{

flag=0;

k++;

for(int i=0;i<n;i++)

{

scanf("%lf%lf",&x,&y);

if(y>d) flag=1;

range[i].left=x-sqrt(d*d-y*y);

range[i].right=x+sqrt(d*d-y*y);

}

if(flag)

{

printf("Case %d: -1/n",k);

continue;

}

sort(range,range+n,cmp);

currentRight=range[0].right;

cnt=1;

for(int i=1;i<n;i++)

{

if(range[i].right<=currentRight) currentRight=range[i].right;

else if(range[i].left>currentRight) cnt++,currentRight=range[i].right;

}

printf("Case %d: %d/n",k,cnt);

}

return 0;

}