题解 UVA1193【Radar Installation】

本人博客

对于x轴上的每个小岛，可以计算出x轴上一段能够管辖它的区间l[i]~r[i]。问题转化为：给定N个区间，在x轴上放置最少的点，使每个区间至少包含一个点。

然后就是贪心操作了，将每个区间按照左端点l[i]从小到大排序，用一个变量来维护已经安放的最后一个监控设备的坐标pos，开始时pos为负无穷。

首先对于每个区间l[i]~r[i]，有两种选择：

1.使用已有的监控设备管辖它

2.建造一台新的设备管辖它

我们的贪心策略是，可以选择1的时候不会选择2

依次考虑每个区间。如果当前区间i的左端点l[i]大于最后一台监控设备的坐标pos，则新增一台监控设备，并令pos=r[i]
（监控尽量向右放），否则就让最后一台已经安放的监控设备来管辖当前区间，并令pos=min(r[i],pos)。

for(int i=1;i<=n;i++)
{
    if(a[i].l>pos)
    {
        ans++;
        pos=a[i].r;
    }
    else pos=min(pos,a[i].r);
}

见代码：

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
inline int read()
{
    int ans=0,flag=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){flag|=ch=='-';ch=getchar();}
    while('0'<=ch&&ch<='9'){ans=(ans<<1)+(ans<<3)+(ch^48);ch=getchar();}
    return flag?-ans:ans;
}
inline double min(double x,double y){return x<y?x:y;}
struct point{
    double l,r;
}a[1005];
int d,bj=0;
bool cmp(const point &x,const point &y){return x.l<y.l;}
void jisuan(int i,double x,double y)
{
    double t=d*d-y*y;
    if(t<0){bj=1;return;}
    a[i].l=x-sqrt(t);
    a[i].r=x+sqrt(t);
}
int main()
{
    int n;
    while(~scanf("%d %d",&n,&d)&&n!=0&&d!=0)
    {
        if(n==0&&d==0)break;
        bj=0;
        for(int i=1;i<=n;++i)
        {
            int x,y;
            x=read();y=read();
            jisuan(i,x,y);
        }
        if(bj==1||d<0)
        {
            printf("-1\n");
            continue;
        }
        sort(a+1,a+n+1,cmp);
        double pos=-0x7fffffff/2;
        int ans=0;
        for(int i=1;i<=n;++i)
        {
            if(a[i].l>pos)
            {
                ++ans;
                pos=a[i].r;
            }
            else pos=min(pos,a[i].r);
        }
        printf("%d\n",ans);
    }
    return 0;
}
/*
3 2
1 2
-3 1
2 1

1 2
0 2

0 0
*/