UVa 1615, Highway
发布时间
阅读量：
阅读量
题意：
在平面上给定n个点以及一个数值D，目标是在x轴上选取尽可能少的点，确保每个原始点都存在一个被选中的点，其欧几里得距离不超过D。
分析：
该问题本质上可以转化为区间覆盖问题。
通过结合n个点的坐标位置及其高度，可以确定每个点对应的x轴上可选点的范围。
随后采用贪心策略，按照区间的右端点进行排序，并优先选取区间的右侧位置。
代码：
#include<bits/stdc++.h>
#define LL long long
#define ms(s) memset(s, 0, sizeof(s))
using namespace std;
const int maxn = 1e5 + 10;
struct Node {
double x, h;
double l, r;
friend bool operator < (const Node& n1, const Node& n2) {
return n1.r < n2.r;
}
}node[maxn];
int main() {
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdo全部评论 (0)
还没有任何评论哟~