给一些区间,挑出最少的区间覆盖 【0,L】
贪心:从0往后,每次挑出R 点最大的
#include <iostream> #include <algorithm> #include <cstring> #include <cmath> using namespace std ; const int N=1e5; int n; struct T{ double x,y; }; T a[N]; int cmp(T x,T y){ return x.x<y.x; } void solve(double end){ double cur=0; int i=1, ans=0; while(cur<end){ ans++; double t=cur; for(;a[i].x<=t&&i<=n;i++) cur=max(cur,a[i].y); if(cur==t&&t<end){ cout<<-1<<endl; return ; } } cout<<ans<<endl; } int main(){ int i,tmp; double x,L,h,r; int cas; cin>>cas; while(cas--){ cin>>tmp>>L>>h; n=0; for(i=1;i<=tmp;i++){ cin>>x>>r; if(r<h/2) continue; n++; a[n].x=x-sqrt(r*r-h*h/4); a[n].y=x+sqrt(r*r-h*h/4); } sort(a+1,a+1+n,cmp); solve(L); } }
标签:1424,覆盖,int,一本,cas,区间,include From: https://www.cnblogs.com/towboa/p/17161429.html