(贪心)

时间复杂度

O(nlogn)

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m,d,cnt;
typedef pair<double ,double> PDD;
PDD segs[N];
double cmp(PDD s1,PDD s2)//按右端点从小到大排序
{
    return s1.second<s2.second;
}
int main()
{
    bool is=false;
    cin>>n>>d;
    for(int i=0;i<n;i++)
    {
        int l,r;cin>>l>>r;
        if(r>d)
        {
            is=true;
            break;
        }
        double x=sqrt(d*d-r*r);
        segs[i]={l-x,l+x};//对于任意一个小岛 (l,r)
        //，我们都可以在海岸线上求出能覆盖该小岛的建造雷达的区间 [l-x,l+x]
    }
    if(is) puts("-1");
    //将所有小岛转化成区间后，问题转化为：给定 n个区间，在 x 轴上选择尽量少的点
    //使得所有区间至少包含一个点。
    else
    {
    sort(segs,segs+n,cmp);
    double last=-1e10;
    for(int i=0;i<n;i++)
    {
        if(segs[i].first>last)
        {
            last=segs[i].second;//新线段左端出界则更新新的右端点
            cnt++;
        }
    }
    cout<<cnt<<endl;
    }
    return 0;
}