当前位置: 首页 > 工具软件 > Radar > 使用案例 >

【贪心】Radar Installation

薛淳
2023-12-01

题目

题目地址:Radar Installation


思路

看到这道题感慨万千。数算实习上机考试打过照面,再次见到仍然是一样的不会做。
对于每个点,都在坐标轴上求出可以覆盖的区域。对所有的区域进行区间右端递增顺序按照排序;右端相同时,左端大的区间排在前面(很显然,此时如果在相对较小的区间当中设定哨点,则一定可以覆盖较大的区间)。
之所以按照这种方式排序,其实也是采用了贪心的想法:对于每个区间, 选择右边界设置哨点, 因为这个位置可以覆盖较多区间; 如果选择右边界之前的点为哨点, 那么把它换成最右的点之后, 以前能被覆盖的区间, 现在仍然得到满足, 所以选择右边界就是贪婪选择。


代码

#include<iostream>
#include<algorithm>
using namespace std;
struct Range
{
    double l;
    double r;
}range[1001];
bool cmp(Range a, Range b) // 注意排序规则,按照right从小到大排序
{
    if (a.r == b.r) // 右坐标相等的情况,要选区间小的范围(一定可以扫射到区间范围大的岛),即让左坐标大的排在前面。
        return a.l > b.l;
    return a.r < b.r;
}
int main()
{
    int n, d, cnt = 0;
    double x, y;
    while (1) {
        cin >> n >> d;
        if (!n)
            break;
        bool flag = d >= 0;
        for (int i = 0; i < n; ++i) {
            cin >> x >> y;
            flag = flag && y <= d;
            if (flag) {
                range[i].l = x - sqrt(d * d - y * y);
                range[i].r = x + sqrt(d * d - y * y);
            }
        }
        sort(range, range + n, cmp);
        int rst = -1;
        if (flag) {
            rst = 1;
            double maxr = range[0].r; // 类型!!!
            for (int i = 1; i < n; ++i) {
                if (range[i].l > maxr) { // 那么range[i]就不能被当前的点覆盖住了
                    maxr = range[i].r;
                    ++rst;
                }
            }
        }
        cout << "Case " << ++cnt << ": " << rst << endl;
    }
    system("pause");
}
 类似资料: