AcWing 112. 雷达设备【贪心】【《算法竞赛进阶指南》】

一、题目链接二、题目分析

（一）算法标签（二）解题思路 三、AC代码四、其它题解

AcWing 112. 雷达设备

贪心

每一个小岛 ( x , y ) (x, y) (x,y)(其中 y < = d y<=d y<=d)对应一个雷达可以检测得到的区间 [ x − d 2 − y 2 , x + d 2 − y 2 ] [x - sqrt{d^2-y^2}, x + sqrt{d^2-y^2}] [x−d2−y2 ​,x+d2−y2 ​], 要想雷达个数最少，则尽可能多的覆盖后面的区间，因此将所有区间按右端点排序，每一次选当前区间的最后一个点，如果后面的区间包含这个点，那么就不符合，反之，答案+1
贪心策略：

将所有区间按右端点从小到大排序；依次考虑每个区间：
如果当前区间包含最后一个选择的点，则直接跳过；如果当前区间不包含最后一个选择的点，则在当前区间的右端点的位置选一个新的点；

参考：AcWing 112. 雷达设备 y总题解 贪心证明 算法步骤 时间复杂度分析

解法一:

#include 
#include 
#include 
#include 

using namespace std;

const int N = 1010;

int n, d;

struct Segment {
    double l, r;
    bool operator< (const Segment& seg) const
    {
        return r < seg.r;
    }
}seg[N];


int main()
{
    cin >> n >> d;
    int x, y;
    for (int i = 0; i < n; i ++ )
    {
        scanf("%d%d", &x, &y);
        if (y > d)
        {
            puts("-1");
            return 0;
        }
        double len = sqrt(d * d - y * y);
        seg[i].l = x - len, seg[i].r = x + len;
    }
    
    sort(seg, seg + n);
    
    int res = 0;
    double last = -1e10;
    for (int i = 0; i < n; i ++ )
    {
        if (seg[i].l < last) continue;
        last = seg[i].r;
        res ++ ;
    }
    
    cout << res << endl;
    return 0;
}

AcWing 112. 雷达设备 y总题解 贪心证明 算法步骤 时间复杂度分析

AcWing 112. 图解+超细节分析+朴素解法（适合小白）

AcWing 112. 雷达设备