TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P3662
  • 题目
  • P3662划区灌溉
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    约翰的奶牛们发现山脊上的草特别美味.为了维持草的生长,约翰打算安装若干喷灌器.为简化问题,山脊可以看成一维的数轴,长为L( \(1≤L≤10^6\) ), 而且L-定是一个偶数.
    每个喷灌器可以双向喷灌,并有确定的射程,该射程不短于A,不长于B,A,B( \(1≤A≤B≤10^3\))都是给出的正整数.它所在位置的两边射程内,都属它的灌溉区域.注意,一个喷灌器往左右两边喷射的距离是一样的,比如往左喷的距离是x,那么往右也是x,(A<=x<=B)。
    现要求山脊的每一个区域都被灌溉到,喷灌器不能将水喷到山脊以外的区域,而且喷灌器的灌溉区域不允许重叠, 约翰有N( $1≤N≤10^3$ )只奶牛,每一只都有特别喜爱的草区,第i奶牛喜爱的草区是[Si,Ei],不同奶牛的草区可以重叠(Ei-Si<=2*B).
    现要求,每只奶牛的草区仅被一个喷灌器灌溉. 寻找最少需要的喷灌器数目.

    输入格式

    第一行,两个整数N和L
    第二行,两个整数A和B
    接下来N行,每行两个整数S和E(0 <= S < E <= L),表示每头奶牛喜欢的草区的起止位置

    输出格式

    一行,一个整数,表示最少需要的喷灌器的数量,若无解,输出-1

    样例输入

    样例输入1:
    2 8
    1 2
    6 7
    3 6

    样例输入2:
    4 202
    10 12
    21 27
    32 39
    103 121
    163 180

    样例输出

    样例输出1:
    3

    样例输出2:
    10

    提示

    样例1说明:

                 |-----c2----|-c1|       每头奶牛喜欢的区域
    
     |---1---|-------2-------|---3---|   喷灌器
    
     +---+---+---+---+---+---+---+---+
    
     0   1   2   3   4   5   6   7   8
    

    来源  usaco 2004 dec gold