区间覆盖问题
问题重述：
给你n个区间[a,b]，选择尽量少的区间去覆盖一条指定的线段[s,t].
算法分析：
我们可以先对a进行排序，从小到大。然后，在选择一个起点在前一个区间终点内的最大区间（如果，找不到则说明没法覆盖指定的线段）。就这样一直遍历下去直到找到可以覆盖整条线段的解为止。
上面讲的是什么意思呢？直白一点，举个例子：
------->我们假设前一个区间[s1,e1]。则，我们可以遍历，起点小于s1的所有区间，然后找到一个终点最大的一个区间即可。如果，在[s1,e1]内找不到起点比s1小的区间。则，说明找不到区间可以覆盖指定的线段[s,t].此时，直接跳出无需再遍历了。
实战演习：Click Here~
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int N = 1E4 + 5;
struct Point
{
double a,b;
bool operator < (const Point x)const
{
if(x.a != a)
return a < x.a;
return b > x.b;
}
};
int main()
{
Point p[N];
int T,n;
scanf("%d",&T);
while(T--)
{
int k = 0;
double w,h,x,r,t;
scanf("%d%lf%lf",&n,&w,&h);
for(int i = 0;i < n;++i){
scanf("%lf%lf",&x,&r);
if(2.0*r <= h)continue;
t = sqrt(r*r-h*h/4.0);
p[k].a = (x-t)>0?(x-t):0;
p[k].b = (x+t)>w?w:(x+t);
k++;
}
sort(p,p+k);
if(p[0].a > 0){
printf("0\n");
continue;
}
int cnt = 1; //最后的一个区间无法加入，所以提前增加
double b = 0,e = 0; //前一区间结束的位置
for(int i = 0;b < w&&i < k;++i) // !!!!b < w 防止多算一个
{
if(p[i].a <= e){
b = max(p[i].b,b); //选择尽量大的区间
}else
{
e = b; //更换新的区间
cnt++;
}
if(p[i].a <= e){ //已经找到了最长的一个区间后
b = max(p[i].b,b);
}else
{
break;
}
}
printf("%d\n",b >= w?cnt : 0);
}
return 0;
}