TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P2273
  • 题目
  • P2273【HN09 day1】邪恶的大叔
    限制 : 时间限制 : 10000 MS   空间限制 : 565536 KB
    问题描述

    一个邪恶的大叔进入了这个神秘的空间,他发现这里有很多很多的Loli在这里,这个邪恶的大叔想把她们全部推倒!但是推倒Loli要耗费的体力太大了,所以他想用尽量少的次数把他们全部推倒。
       所有的Loli可以抽象成一个一维的坐标系,第i个Loli所在的位置为Xi,她的身高为Hi。大叔可以推倒任意个Loli让她们向左或者向右倒下去,第i个Loli倒下去之后可能会连带着别的Loli一起倒下去(向左倒就是在她左边并且满足|Xi-Xj|≤Hi的所有Loli也会一起向左倒,向右同样计算)。
       你的任务是帮助大叔计算出最少推倒多少个Loli可以让所有的Loli全部倒下。

    输入格式

    第一行一个整数N,表示Loli的个数。
      以下N行每行两个整数Xi Hi,分别表示第i-1个Loli的位置和她的身高。
      输入保证Xi递增输入。

    输出格式

    输出一行一个整数,表示大叔最少推倒的次数。

    样例输入

    6
    1 1
    2 2
    3 1
    5 1
    6 1
    8 3

    样例输出

    2

    提示

    【样例解释】

       向右推倒第1个Loli可以让第2、3个Loli一起倒下。
       向左推倒第6个Loli可以让第5、6个Loli一起倒下。
    【数据约定】

       对于30%的数据,满足N≤10
       对于50%的数据,满足N≤1000
       对于100%的数据,满足N≤100000;Hi≤108;Xi≤231。