UVA 10382 Watering Grass（区间覆盖，贪心）题解

题意：有一块草坪，这块草坪长l 米，宽 w 米，草坪有一些喷头，每个喷头在横坐标为 p 处，每个喷头的纵坐标都是(w/2) ，并且喷头的洒水范围是一个以喷头为圆心，半径为 r 米的圆。每次最少需要打开多少个喷头来给草坪洒水，并且草坪各处都能被洒到，不行输出-1

思路：这是一道区间覆盖（贪心）题：

有一堆区间 l1, r1；l2, r2...ln，rn，问你最少用几个能覆盖0~P的长度

那么我们先按照L升序排序，far是目前所能找到的最远处，R是上一次查询所能找到的最远处，每次查询我们都要找后面满足li <= R的点，记录far，当这一轮查找完毕后R = far。显然R初始化应为最左端的点（本题为0）。

比如区间为[-1,4]，[0,2]，[0,1]，[2,4]，[2,6]，[3,5]，[3,6]，[3,7]，[6,8]，覆盖区域为0~8

第一步选择[-1,4]，[0,2]，[0,1]中最远的[-1,4] ，那么下一步能够选择的有[2,6]，[3,5]，[3,6]，[3,7]，由于7最大，所以下一步选择[3,7]，最后一步只能选择[6,8]

这一题注意筛选 r < w 情况。

代码：

#include<set>

#include<map>

#include<stack>

#include<cmath>

#include<queue>

#include<vector>

#include<string>

#include<cstdio>

#include<cstring>

#include<sstream>

#include<iostream>

#include<algorithm>

typedef long long ll;

using namespace std;

const int maxn =  + ;

const int MOD = 1e9 + ;

const int INF = 0x3f3f3f3f;

struct node{

    double l, r;

    bool operator < (const node x) const{

        return l < x.l;

    }

}a[maxn];

int n;

double l, w;

int solve(){

    sort(a + , a + n + );

    double far = , R = ;

    int ans = , pos = ;

    while(pos <= n){

        if(far >= l) break;

        if(a[pos].l <= R){

            ans++;

            while(a[pos].l <= R && pos <= n){

                far = max(far, a[pos].r);

                pos++;

            }

            R = far;

        }

        else break;

    }

    if(far >= l) return ans;

    return -;

}

int main(){

    while(~scanf("%d%lf%lf", &n, &l, &w)){

        w /= 2.0;

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

            double p, r, del;

            scanf("%lf%lf", &p, &r);

            if(r >= w){

                double s = sqrt(r * r - w * w);

                a[i].l = p - s;

                a[i].r = p + s;

            }

            else{

                i--;

                n--;

            }

        }

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

    }

    return ;

}

巴特西

UVA 10382 Watering Grass（区间覆盖，贪心）题解

最新文章

热门文章