112. 雷达设备(贪心)

https://www.acwing.com/problem/content/114/
典型区间贪心
题目要求寻找最少雷达摆放数,范围覆盖所有岛
读题后一开始想的是雷达放在x轴何处,但是这样直接想太难了,而且有关于圆的操作,不利于判断
于是转换角度(改变主体),从岛的角度看,雷达可以摆在x轴的那些地方,这样就变成区间了
即,我们不考虑每个雷达可以覆盖哪些小岛,而是每个小岛可以在哪些区间摆放雷达
对于每一个岛,雷达摆放在x轴上都有一个区间,只要不超过区间,就可以覆盖到岛

那么问题就转变为求给定若干区间,求最少需要多少点,可以满足所有区间都包含点

那么有n个岛,就有n个区间,将n个区间以右端点排序,区间之间有的有交集,有的没有
有交集的就说明在这个交集内,雷达可以覆盖这两个岛
贪心策略:
对于每个区间:
1.要是上一个点不在此区间范围内,就说明上一个区间和此区间没有交集,必然要用两个点去覆盖这两个区间,放右端点
2.要是上一个点在此区间范围内,说明这个区间以及被满足条件了,则跳到下一区间继续判断

严格证明:
这里利用通用的证明方式:cnt表示这个算法的结果,opt表示最佳解,我们的目标是证明cnt=opt.
通用的证明等于的方式,即要证明cnt>=opt且cnt<=opt
根据定义,显然有1.opt<=cnt,我们算法的解一定是大于等于最佳解的,这个式子一定成立
2.证明opt>=cnt,即等价于证明 所有可行解>=cnt (放缩,opt是所有解的子集)
根据我们的贪心策略,上一个点所在的区间必定是在现在区间的左端点左边,即两个区间不相交
若我们选了cnt个点:就说明存在cnt个不相交的区间
有cnt个互不相交的区间,因为要满足所有区间都要包含点,区间之间没有交集,无法共用一个点,于是我们的点数必定>=cnt,至少为cnt个
故得证,所有可行解必然>=cnt,故opt必然>=cnt
故证cnt=opt

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int N = 1e3+10;
int n,d;
int x,y;
int cnt;
struct line
{
    double l,r;
}l[N];

bool cmp(line a,line b)
{
    return a.r<b.r;
}

int main()
{
    cin >> n >> d;
    for(int i=0;i<n;i++)
    {
        cin >> x >> y;
        double width=sqrt(d*d-y*y);
        l[i]={x-width,x+width};
        if(y>d)
        {
            cout << -1 << endl;
            return 0;
        }
    }
    sort(l,l+n,cmp);
    double last = -1e4;
    for(int i=0;i<n;i++)
    {
        if(l[i].l>last)
        {
            last=l[i].r;
            cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}