信息学奥赛一本通T1424：喷水装置

【题目描述】

长L 米，宽 WW 米的草坪里装有 n 个浇灌喷头。每个喷头都装在草坪中心线上（离两边各 W/2 米）。我们知道每个喷头的位置（离草坪中心线左端的距离），以及它能覆盖到的浇灌范围。

请问：如果要同时浇灌整块草坪，最少需要打开多少个喷头？

【输入】

输入包含若干组测试数据。

第一行一个整数 T 表示数据组数；

每组数据的第一行是整数 n、L 和 W；

接下来的 n 行，每行包含两个整数，给出一个喷头的位置和浇灌半径（上面的示意图是样例输入第一组数据所描述的情况）。

【输出】

对每组测试数据输出一个数字，表示要浇灌整块草坪所需喷头数目的最小值。如果所有喷头都打开也不能浇灌整块草坪，则输出 -1

【输入样例】

3
8 20 2
5 3
4 1
1 2
7 2
10 2
13 3
16 2
19 4
3 10 1
3 5
9 3
6 1
3 10 1
5 3
1 1
9 1

【输出样例】

6
2
-1

【源程序】

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#define EPS 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LL long long
const int MOD = 1E9+7;
const int N = 100000+5;
const int dx[] = {-1,1,0,0,-1,-1,1,1};
const int dy[] = {0,0,-1,1,-1,1,-1,1};
using namespace std;
struct Node{
    double pos;
    double num;
    bool operator < (const Node &rhs)const{
        return pos<rhs.pos;
    }
}node[N];
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        int n,l,w;
        scanf("%d%d%d",&n,&l,&w);

        int cnt=0;
        for(int i=1;i<=n;i++){
            int pos,r;
            scanf("%d%d",&pos,&r);
            if(r>w/2){
                node[++cnt].pos=pos-sqrt(r*r-(w/2.0)*(w/2.0));
                node[cnt].num=pos+sqrt(r*r-(w/2.0)*(w/2.0));
            }
        }
        sort(node+1,node+1+cnt);

        double len=0;
        int res=0;
        bool flag=true;
        int i=1;
        while(len<l){
            res++;
            double pos=len;
            while(node[i].pos<=pos&&i<=cnt){
                if(len<node[i].num)
                    len=node[i].num;
                i++;
            }
            if(len==pos&&pos<l){
                printf("-1\n");
                flag=false;
                break;
            }
        }
        if(flag)
            printf("%d\n",res);
    }
    return 0;
}

信息学奥赛一本通T1424：贪心算法 喷水装置 归属于 贪心算法，更多同类题解源程序见：贪心算法 和 喷水装置