题解 | #可达性#

思路

看到圆就很想吐，但幸好想到了每个圆代表的区间其实就是
所以问题就转化为：最少能用多少个子区间将总区间表示出来。
然后是怎么选区间的问题，只要将每个区间排序，然后贪心地去选就好了。
先排序，每个区间L小在前，然后是R大在前，然后只要我没有达到最大长度，
就选一个区间使得我能到达最远的距离，然后ans++，如果选完n个都无法达到那个长度，
就输出-1，否则输出ans。
做法是O(n^2)的，应该有更优的，但这个数据范围够用了。

代码

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm> 
using namespace std;
const int maxn=15005;

struct C{
    double l,r;
}s[maxn];

int t,n,cnt;
double L,w,x,r;

bool cmp(C a,C b){
 if(a.l==b.l) return a.r>b.r;
 return a.l<b.l;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>t;
    while(t--){
        cnt=0;
        cin>>n>>L>>w;
        for(int i=1;i<=n;i++){
               cin>>x>>r;
               if(r*2<=w) continue;
               s[++cnt].l=x-sqrt(r*r-w*w/4);
               s[cnt].r=x+sqrt(r*r-w*w/4);
          }
          sort(s+1,s+1+cnt,cmp);
      //    for(int i=1;i<=cnt;i++)    cout<<s[i].l<<" "<<s[i].r<<endl;  
        double idx=0,mx=0;
          int ans=0; 
          for(int i=1;i<=cnt;i++){ //最多是打开cnt个喷头 
               for(int j=1;j<=cnt;j++){
                if(s[j].r>idx&&s[j].l<=idx){ //达到要求更进一步 
                    if(mx<s[j].r) mx=s[j].r; //取能够到的最远距离 
                } 
               }
               ans++; //打开了一个喷头 
               idx=mx; 
           //    cout<<idx<<" "<<ans<<" "<<L<<endl;
               if(idx>=L) break; //达到目的 
          }
          if(idx>=L) cout<<ans<<"\n";
          else cout<<-1<<"\n";
    }
    return 0;
}