本文主要是介绍喷水装置二---耗时两天，感觉只是会这道题而已，区间贪心，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
地址：http://acm.nyist.net/JudgeOnline/problem.php?pid=12
题目：
喷水装置（二）
- 描述
- 有一块草坪，横向长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
- 第一行输入一个正整数N表示共有n次测试数据。
思路：
这道题，测试用例都是费的，我之前的做法就一直是wrong answer.测试用例过了，不代表能过。最主要是把问题分析好。很明显就是排序，然后不断的试，看是否符合条件
（贪心）。。但是关键就是在这个条件的判断。
从这里http://blog.csdn.net/pointerking/article/details/22686001 了解到了该怎么解决，虽然耗尽心思，觉得懂了，但不担保，同类型的会动。只是觉得很神奇，很佩服想
到是怎么做的。不买关子先，直接解释下。。
首先对读入的数据要做一次判断：
if(NodeArrArr[i].r<=h/2){ //不能构成一个完整的三角形，斜边要大于直角边i--;n--;continue;}也就是半径要大于直角边：
只有构成了这种情况，才能临界覆盖整个长方向。
接着：
NodeArrArr[i].left=NodeArrArr[i].x-Math.sqrt(NodeArrArr[i].r*NodeArrArr[i].r-h*h/4);
将情况分为left和right。
left有三种情况
==0，是临界，<0肯定是可以的，>0肯定不满足
而右边的情况：NodeArrArr[i].right=NodeArrArr[i].x+Math.sqrt(NodeArrArr[i].r*NodeArrArr[i].r-h*h/4);
只有大于长度w的情况，和<w的情况。
感觉自己还是讲得不够清楚，可以讲案例的数据带进去，模拟下，画下图就可以理解了。进行实践才是最好的学习方式。
import java.util.Scanner;
/** 170 662 * 喷水装置二*/
public class Main1{public static void main(String[] args){Scanner sc=new Scanner(System.in);int m=sc.nextInt();while(m-->0){int n=sc.nextInt();double w=sc.nextDouble();double h=sc.nextDouble();NodeArr[] NodeArrArr=new NodeArr[n];for(int i=0;i<n;i++){NodeArrArr[i]=new NodeArr();NodeArrArr[i].x=sc.nextDouble();NodeArrArr[i].r=sc.nextDouble();if(NodeArrArr[i].r<=h/2){ //不能构成一个完整的三角形，斜边要大于直角边i--;n--;continue;}//NodeArrArr[i].r*NodeArrArr[i].r-h*h/4--得到刚好能覆盖长方形的情况，看是否给出的数据符合NodeArrArr[i].left=NodeArrArr[i].x-Math.sqrt(NodeArrArr[i].r*NodeArrArr[i].r-h*h/4);NodeArrArr[i].right=NodeArrArr[i].x+Math.sqrt(NodeArrArr[i].r*NodeArrArr[i].r-h*h/4);}NodeArrArr=insertSort(NodeArrArr,n); //直接插入排序，从大到小int count=0;int flag=0;double max=0,begin=0;for(int i=0;i<n;i++){while(i<n&&NodeArrArr[i].left<=begin){ //由最大的开始，负数，就一定可以覆盖，就左边而言if(NodeArrArr[i].right>max) //在上面的情况下，找到最大的--right=x+need,下面的与w判断max=NodeArrArr[i].right;i++;}i--; //不怕越界，后面有判断出去的。//每次都要判断一下Max的值，看是否已经出界，若出界则跳出，否则继续贪心if(max>=w){count++;begin=max;break;}else if(begin<max){ //Max不出界，则正常向右贪心count++;begin=max;}else{ //两点以上的中间会有断点flag=1;break;}}if(flag==1||begin<w){ //右边盖不住 System.out.println("0");}else{System.out.println(count);}}}public static NodeArr[] insertSort(NodeArr[] arr,int length){double key1,key2;for(int i=1;i<length;i++){int j=i-1;key1=arr[j].left;key2=arr[j].right;while(j>0&&key1<arr[j-1].left){arr[j].left=arr[j-1].left;arr[j].right=arr[j-1].right;j--;}arr[j].left=key1;arr[j].right=key2;}return arr;}}
class NodeArr{double x,r,left,right;
}最后补充下知识点--区间的贪心：http://shu-mj.com/archives/167
这篇关于喷水装置二---耗时两天，感觉只是会这道题而已，区间贪心的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
