NYOJ 喷水装置（二）

题目转换成，每个水龙头在横坐标方向上覆盖的长度区间，转换后的问题就有点像会场安排问题了，然后接下来选的方案依据贪心，我们队这些个区间进行排序，依照区间的左端点按从小到大排序，然后从左往右选取，条件是当前区间的左端点在覆盖范围内，右端点最远。如果一次循环覆盖范围没有加大，就证明不能覆盖。

 1 #include<iostream>
 2 #include<cmath>
 3 #include<stdlib.h>
 4 #include<string.h>
 5 
 6 
 7 using namespace std;
 8 
 9 typedef struct
10 {
11     double start;
12     double end;
13 }SE;
14 
15 SE a[10002];
16 
17 int compare (const void *p1, const void *p2)
18 {
19     return (((SE *)p1)->start<((SE *)p2)->start)? 1:-1;
20 }
21 
22 int main()
23 {
24     int T;
25     cin>>T;
26     while(T--)
27     {
28         int N;
29         double w, h;
30         cin>>N>>w>>h;
31         for(int i=0; i<N; i++)
32         {
33             double x, r;
34             cin>>x>>r;
35             double tem = r*r-((double)h/2)*((double)h/2);
36             if(tem>=0)
37                 tem = sqrt(tem);
38             else
39                 tem = 0;
40             a[i].start = x - tem;
41             a[i].end = x+ tem;
42         }
43         qsort(a,N,(sizeof(a[0])),compare);
44         /*for(int i=0; i<K; i++)
45         {
46             cout<<a[i].start<<"    "<<a[i].end<<endl;
47         }*/
48         double st=0, en=0;
49         int visit[1002];
50         memset(visit,0,sizeof(visit));
51         int num = 0;
52         while(en<w)
53         {
54             double endest = en;
55             for(int i=0; i<N; i++)
56             {
57                 if(visit[i]==0&&a[i].start<=en&&a[i].end>endest)
58                 {
59                     endest = a[i].end;
60                 }
61             }
62             if(endest>en)
63             {
64                 en = endest;
65                 num++;
66             }
67             else
68             {
69                 cout<<0<<endl;
70                 break;
71             }
72         }
73         if(en>=w)
74         {
75             cout<<num<<endl;
76         }
77     }
78     return 0;
79 }