NYOJ 喷水装置（二）贪心+ 区间覆盖

本文主要是介绍NYOJ 喷水装置（二）贪心+ 区间覆盖，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

描述

有一块草坪，横向长w,纵向长为h,在它的橫向中心线上不同位置处装有n(n<=10000)个点状的喷水装置，每个喷水装置i喷水的效果是让以它为中心半径为Ri的圆都被润湿。请在给出的喷水装置中选择尽量少的喷水装置，把整个草坪全部润湿。

输入

第一行输入一个正整数N表示共有n次测试数据。
每一组测试数据的第一行有三个整数n,w,h，n表示共有n个喷水装置，w表示草坪的横向长度，h表示草坪的纵向长度。
随后的n行，都有两个整数xi和ri,xi表示第i个喷水装置的的横坐标（最左边为0），ri表示该喷水装置能覆盖的圆的半径。

输出

每组测试数据输出一个正整数，表示共需要多少个喷水装置，每个输出单独占一行。
如果不存在一种能够把整个草坪湿润的方案，请输出0。

样例输入

2
2 8 6
1 1
4 5
2 10 6
4 5
6 5

样例输出

1
2

思路：把覆盖面积问题转化为水平长度覆盖问题，如上图最后一个圆的红线就是该喷水装置可以覆盖的最大水平距离。

这题然后贪心：先按照起始位置从小到大排序，然后每次选择起点在当前覆盖范围内并且终点尽可能远的点，并更新覆盖距离。

如果发现 某一轮不能找到覆盖更远的点，说明不能完全覆盖。

#include<bits/stdc++.h>
using namespace std;struct Node{double s,e;bool operator<(const Node o)const{return s < o.s;		}
}nodes[10000+5];
int t,n,w,h;
int main(){scanf("%d",&t);int x,r;while(t--){int cnt = 0;scanf("%d%d%d",&n,&w,&h);for(int i = 0; i < n; ++i){scanf("%d%d",&x,&r);if(r >= 1.0*h/2){nodes[cnt].s = x-sqrt(r*r-1.0*h/2);nodes[cnt].e = x+sqrt(r*r-1.0*h/2);++cnt;} }sort(nodes,nodes+cnt);bool flag = true;double ma = 0,mi = w;if(nodes[0].s > 0){printf("0\n");continue;}int ans = 0;double cover = 0; //总的覆盖长度int cur_max = 0;while(cover < w){//进入循环则说明目前没有完全覆盖cur_max = 0;//本轮最大覆盖长度 for(int j = 0; j < cnt && nodes[j].s <= cover; ++j){//新的区间起点需要在当前覆盖的长度内if(nodes[j].e-cover > cur_max){ //判断是否有更长的区间cur_max = nodes[j].e-cover;}}if(cur_max == 0){//本轮没有获得一个区间，说明没有起点在cover内并且终点在cover外更远的点，即不能实现完全覆盖flag = false;break;} else{++ans;cover += cur_max; //更新当前覆盖的长度}}if(!flag){printf("0\n");continue;}printf("%d\n",ans);//			for(int i = 0; i < cnt; ++i){
//				printf("%lf %lf\n",nodes[i].s,nodes[i].e);
//			} }return 0;}

这篇关于NYOJ 喷水装置（二）贪心+ 区间覆盖的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---