NYOJ 12 喷水装置（二）（区间问题）

喷水装置（二）

时间限制：3000 ms | 内存限制：65535 KB

难度：4

描述: 有一块草坪，横向长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：求得每个喷水装置的覆盖x轴上区间[left,right]，按左对区间（结构体）排序，sum表示已覆盖区域[0,sum],max用来表示延伸长度，详细见代码1：

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<math.h>
 4 #include<algorithm>
 5 using namespace std;
 6 struct ps
 7 {
 8     double left;
 9     double right;
10 }w[10001];
11 bool comp(ps a,ps b)//按左排序
12 {
13     if(a.left<b.left) return true;
14     return false;
15 }
16 int main()
17 {
18     int ncases,n,i,width,h,x,r,count,flag;
19     double sum,max;
20     scanf("%d",&ncases);
21     while(ncases--)
22     {
23         flag=1;sum=0;count=0;
24         scanf("%d %d %d",&n,&width,&h);
25         for(i=0;i<=n-1;i++)
26         {
27             scanf("%d %d",&x,&r);
28             if(r>h/2.0) {
29                 w[i].left=x-sqrt((double)r*r-(double)h/2.0*h/2.0);
30                 w[i].right=x+sqrt((double)r*r-(double)h/2.0*h/2.0);
31             }else {i--;n--;}
32         }
33         sort(w,w+n,comp);
34         while(sum<width)//算法关键
35         {
36             max=0;//向右延长最大值
37             for(i=0;i<=n-1&&w[i].left<=sum;i++)//w[i].left<=sum保证装置相交
38             {
39                 if((w[i].right-sum)>max)
40                 {
41                     max=w[i].right-sum;//w[i].left>sum，max未变=0
42                 }
43             }
44             if(max==0)//未能相交
45             {
46                 flag=0;
47                 break;
48             }
49             else
50             {
51                 sum=sum+max;//更新能够覆盖的宽度
52                 count++;
53             }
54         }
55         if(flag==1)
56         {
57             printf("%d
",count);
58         }
59         else
60         {
61             printf("0
");
62         }
63     }
64     return 0;
65 }

View Code

分析思路2:右排序，详细见代码2：（便于理解，附上qsort函数的用法地址：http://www.slyar.com/blog/stdlib-qsort.html）

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #include<math.h>
 4 typedef struct{
 5    double a;//左
 6    double b;//右
 7 }W;
 8 int cmp(const void *a,const void *b){//右排序
 9      return (*(A*)a).b-(*(A*)b).b;
10 }
11 int main()
12 {
13       int N,n,w,h,i,j,x,r,count,len;
14       W d[10000];
15       scanf("%d",&N);
16       while(N--)
17          {
18              scanf("%d %d %d",&n,&w,&h);
19              for(i=0,j=0;i<n;i++){
20                scanf("%d %d",&x,&r);
21                if(r>h/2){
22                 d[j].a=x-sqrt(r*r-h*h*1.0/4);
23                 d[j].b=x+sqrt(r*r-h*h*1.0/4);
24                 j++;//去掉不符合条件的
25                }
26             }
27        n=j;
28        qsort(d,n,sizeof(A),cmp);//右排序
29        count=0;len=0;j=-1;
30        while(len<w){//存在交点，但未能到达右边界
31        for(i=n-1;i>j;i--)
32        if(d[i].a<=len)
33             len=d[i].b,count++,j=i;//由右开始寻找可以小于等于len的左边点，（存在循环结束j=a，i=a-1）（不存在循环结束j=i）
34        if(i==j) break;//中间找不到满足条件的左边界
35       }
36   if(len>=w) printf("%d
",count);
37   else printf("0
");
38  }
39 }

View Code