NYOJ 12 喷水装置（二）——————贪心，区间覆盖

ゞ浴缸里的玫瑰 2022-05-11 12:12 197阅读 0赞

## 喷水装置（二） ##

时间限制：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  
2

--------------------

转化为区间覆盖问题  
找到数量最小的区间把\[0,w\]的区间给覆盖住

#include<bits/stdc++.h>
    using namespace std;
    const int MAXN = 1e4+7;
    double x[MAXN],r[MAXN];
    
    struct node
    {
        
            double st,ed;
            node(){
        }
            node(double _st,double _ed)
            {
        
                    st = _st;
                    ed = _ed;
            }
    }l[MAXN];
    
    bool cmp(node x,node y)
    {
        
            return x.st==y.st?x.ed>y.ed:x.st<y.st;
    //        return x.ed>y.ed;
    }
    int main()
    {
        
            int t,n;
            double w,h;
            scanf("%d",&t);
            while(t--)
            {
        
                    int cnt=0;
                    scanf("%d %lf %lf",&n,&w,&h);
                    for(int i=0;i<n;i++)
                    {
        
                            double a,b;
                            scanf("%lf %lf",&a,&b);
                            if(b>h/2.0)
                            {
        
                                    x[cnt]   = a;
                                    r[cnt] = sqrt(b*b-h*h/4.0);
                                    l[cnt].st = x[cnt]-r[cnt]<0?0:x[cnt]-r[cnt];
                                    l[cnt].ed = x[cnt]+r[cnt];
                                    cnt++;
                            }
                    }
    
                    sort(l,l+cnt,cmp);//以开始时间早的优先，开始时间相同结束时间晚的优先排序
    //                for(int i=0;i<cnt;i++)//转化为线段
    //                        printf("st:%.2lf ed:%.2lf\n",l[i].st,l[i].ed);
                    int ans=0;//保存区间数目
                    double f1=0.0;//表示当前的最大覆盖长度
                    double f2=0.0;//表示下个线段的最大覆盖长度
                    for(int i=0;i<cnt;i++)
                    {
        
                            if(l[i].st<=f1+1e-7)
                            {
        
                                    if(l[i].ed>f2)
                                            f2=l[i].ed;
                            }
                            else
                            {
        
                                    f1 = f2;
                                    ++ans;//使用当前区间,故ans++
                                    if(f1 + 1e-7 >=w)  break;//达到要求，
                                    if(l[i].st > f1 + 1e-7)  break;//达到要求
                                    --i;
                            }
                    }
                    if(f2 + 1e-7<w) ans=0;//最后一个区间的末端也无法覆盖到w
                    else if(f1 + 1e-7 < f2) ans++;//
                    printf("%d\n",ans);
    
            }
            return 0;
    }