区间贪心(区间选点)
给定若干区间,最少选多少个点,可以使每个区间上至少有一个点?
贪心策略:
1)将所有区间按右端点排序
2)扫描每一个线段
情况1: 如果上一个点不在区间中,则选右端点
情况2: 如果上一个点在区间中, 则跳过
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdio>
using namespace std;
const int N = 1010;
int n, d;
int cnt; //雷达数量, 记录答案
struct Segment //背板子
{
double l, r;
bool operator < (const Segment &t) const
{
return r < t.r;
}
}seg[N];
int main()
{
bool failed = false;
scanf("%d%d", &n, &d);
for (int i = 0; i < n; i ++ )
{
int x, y;
scanf("%d%d", &x, &y);
if (y > d) failed = true;
double r = sqrt(d * d - y * y);
seg[i] = {x - r, x + r};
}
if (failed) puts("-1");
else
{
sort(seg, seg + n); //按照右端点排序
double last = -1e20;
for (int i = 0; i < n; i ++ )
if (seg[i].l > last)
{
cnt ++ ;
last = seg[i].r;
}
printf("%d\n", cnt);
}
return 0;
}