UVa 1615 Highway （贪心，区间选点问题）

题意：给定一个数 n 个点，和一个d，要求在x轴上选出尽量少的点，使得对于给定的每个点，都有一个选出的点离它的欧几里德距离不超过d。

析：首先这是一个贪心的题目，并且是区间选点问题，什么是区间选点呢，就是说在数轴上有 n 个闭区间，取尽量少的点，使得每个区间都至少有一个点。

一看是不是和这个题很相似，是的，那么区间哪里来呢？自己造呗，既然说是距离不超过ｄ，意思就是在给定的点为圆心，以 d 为半径画圆，在x轴上的区间，

那么区间不就有了么，然后这个怎么贪心呢，是这样的，把所有的区间的右端点从小到大排序（如果相同，则左端点从大到小排），那么贪心策略就是一定取最后一个点，

也就是右端点，想一想为什么，也很好理解，尽量让多的区间都有这个点。那么这个题就很简单了。

代码如下：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

using namespace std;

const int maxn = 1E5 + 5;

struct node{

    double l, r;

    bool operator < (const node &p) const{

        return r < p.r || (r == p.r && l > p.l);//排序

    }

};

node a[maxn];

int main(){

//    freopen("in.txt", "r", stdin);

    int n;

    double x, y, l, d;

    while(scanf("%lf", &l) == 1){//l 并没有发现有什么用

        scanf("%lf %d", &d, &n);

        for(int i = 0; i < n; ++i){

            scanf("%lf %lf", &x, &y);

            a[i].l = x - sqrt(d*d - y*y);//计算左端点

            a[i].r = x + sqrt(d*d - y*y);//计算右端点

        }

        sort(a, a+n);

        int cnt = 1;

        double ans = a[0].r;//取最后一个点

        for(int i = 0; i < n; ++i)

            if(a[i].l > ans){//如果这个不包含了，先下一个右端点

                ++cnt;

                ans = a[i].r;

            }

        printf("%d\n", cnt);

    }

    return 0;

}

巴特西

UVa 1615 Highway （贪心，区间选点问题）

最新文章

热门文章