UVA - 10382 Watering Grass区间完全覆盖问题

n sprinklers are installed in a horizontal strip of grass l meters long and w meters wide. Each sprinkler is installed at the horizontal center line of the strip. For each sprinkler we are given its position as the distance from the left end of the center line and its radius of operation. What is the minimum number of sprinklers to turn on in order to water the entire strip of grass? Input Input consists of a number of cases. The first line for each case contains integer numbers n, l and w with n ≤ 10000. The next n lines contain two integers giving the position of a sprinkler and its radius of operation. (The picture above illustrates the first case from the sample input.) Output For each test case output the minimum number of sprinklers needed to water the entire strip of grass. If it is impossible to water the entire strip output ‘-1’. Sample Input 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 Sample Output 6 2 -1

问题连接

问题描述

水平带上有一块长l，宽w的草坪，草坪的水平中心线上有n个洒水器，并给出它们的位置和它们洒水的范围。问最少使用多少个洒水器可以让整块草坪都能被水淋到。如果能则输出最小的数目，否则输出-1。

问题分析

贪心策略：从左往右添加区间，在能添加区间的前提下，选择右端点最大的区间。

代码如下

#include<algorithm> #include<cstdio> #include<cmath> using namespace std; const int N=1e4+5; struct point{//区间的左右端点值 double l,r; }pa[N]; bool cmp(const point&a,const point&b){ return a.r>b.r; } /* 从左到右覆盖区间，所以把区间右端点大的排前面。这样对于相同的左边界才能尽可能扩大区域。 比如已经覆盖到区域[0,x]，那么下一个区域只需要满足左端点在x的左边， 但显然左端点不影响区域大小，而右端点要尽可能大，才能让使用的区间少 */ int main(){ int i,n,num,count,maxn; double x,r,l,w,halfw2,end; while(scanf("%d %lf %lf",&n,&l,&w)!=EOF){ halfw2=w*w/4; num=0; for(i=0;i<n;i++){//将已给的转换为区间 scanf("%lf %lf",&x,&r); if(2*r>w) {//r<=w/2时，不能完全覆盖草坪，选了也没用，所以就不处理了 pa[num].l=x-sqrt(r*r-halfw2); pa[num].r=x+sqrt(r*r-halfw2); num++; } } sort(pa,pa+num,cmp); end=0; count=0; maxn = num; while (end < l) { for (i = 0; i < num; i++) { if (pa[i].l <= end && pa[i].r > end) { end = pa[i].r; maxn = i+1;//避免与第一个循环体最后的if冲突引起死循环 count++; break; } if (i >= maxn) break; /*小优化。提前跳出，因为每次选的区间右端点值是越来越大的， 如果判断到相等就说明以后也不会有合适的区间了。*/ } if (i >= maxn) break;//说明无合适的区间 //整个代码也可以不引入maxn，直接判断if(i==num)时跳出 } if(end<l) printf("-1\n"); else printf("%d\n",count); } return 0; }