学步园

数轴上有n个区间[ai,bi]，选择尽量少的区间覆盖一条指定线段[s,t]。

贪心策略：

把各区间按照a从小到大排序，从前向后遍历，然后每次选择从当前起点S开始的最长区间，并以这个区间的右端点为新的起点，继续选择，直到找不到区间覆盖当前起点S或者S已经到达线段末端。

需要注意的是，如果某一区间边界大于s,t的边界，应把它们变成s或t。因为超出的部分毫无意义，同时还会影响对数据的分析。

经典例题：喷水装置->http://acm.nyist.net/JudgeOnline/problem.php?pid=12

附代码。

#include <math.h>
#include <stdio.h>
#include <algorithm>
using namespace std;
struct Qujian
{
    float a,b;
};
bool cmp(const Qujian& s1,const Qujian& s2)
{
    return s1.a < s2.a;
}
int main()
{
    Qujian A[10005];
    int z,n,w,h,x,r,cnt;
    float start,l,__h;
    scanf("%d",&z);
    while(z--)
    {
        scanf("%d%d%d",&n,&w,&h);
        cnt = start = 0;
        __h = h*h*1.0/4;
        for(int i=0;i<n;i++)
        {
            scanf("%d%d",&x,&r);
            if(r*r < __h)
            {
                i--;n--;
                continue;
            }
            l = sqrt(r*r - __h);
            A[i].a = x-l > 0 ? x-l : 0;
            A[i].b = x+l < w ? x+l : w;
        }
        sort(A,A+n,cmp);
        int i,k = -1;
        while(start < w && A[k+1].a <= start)
        {
            float mmax = -1;
            for(i = k+1;A[i].a <= start && i<n;i++)
                if(mmax < A[i].b)
                {
                    mmax = A[i].b;
                    k = i;
                }
            start = mmax;
            cnt++;
        }
        printf("%d\n",start<w ? 0 : cnt);
    }
	return 0;
}