区间完全覆盖问题（贪心）

题目链接：here

题意：在一个矩形的花坛上，中间水平放了一排喷水装置，浇灌半径为r，问最少需要多少个装置可以润湿整个花坛。

将每个装置转换成一条线段，就变成了求最少的线段覆盖整个区间。

将各线段左端点从小到大排序

设已覆盖区间的右端点为ed

每次贪心选择起点小于ed的线段中右端点最大的那一条，然后更新ed。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=50010;
 4 
 5 struct Seg{
 6     double x,y;
 7     bool operator < (const Seg& a)const{
 8         return x<a.x;
 9     }
10 }s[maxn];
11 
12 int main(){
13     int n;
14     double l,w;
15     int t;
16     scanf("%d",&t);
17     while(t--){
18         scanf("%d%lf%lf",&n,&l,&w);
19         double c,r;
20         w/=2;
21         for(int i=0;i<n;i++){
22             scanf("%lf%lf",&c,&r);
23             if(r<w) s[i].x=s[i].y=0;
24             else{
25                 double x=sqrt(r*r-w*w);
26                 s[i].x=c-x;
27                 s[i].y=c+x;
28             }
29         }
30         sort(s,s+n);
31         if(s[0].x>0){
32             puts("0");
33             continue;
34         }
35         int ans=0;
36         double st=0,ed=0;
37         for(int i=0;i<n;i++){
38             if(s[i].x<=st){
39                 while(i<n&&s[i].x<=st){
40                     ed=max(ed,s[i].y);
41                     i++;
42                 }
43                 i--;
44                 ans++;
45                 st=ed;
46             }
47             if(ed>=l) break;
48         }
49         if(ed>=l) printf("%d
",ans);
50         else puts("0");
51     }
52 }

View Code