TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3668
  • 题目
  • P3668奶牛放火
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    有n堆干草排成一条直线堆放在约翰的农田里。我们可以把它们看成数轴上的点,坐标为x1,x2,...,xn。 
    一只发怒的奶牛想点燃干草堆,以释放内心的不愉快。如果它在第1秒点燃了坐标为x的干草堆,那么该堆干草的引火半径为1,也就是说,在以该草堆为圆心,半径为1的范围内的所有干草堆在第2秒钟都会被点燃。在第2秒被引燃的干草堆接着燃烧,它们的引火半径为2,然后被它们引燃的草堆会在第3秒开始燃烧,它们的引火半径加1,一直这样传递下去...... 
    也就是说如果x草堆是在第y秒被引燃的,那么它们的引火半径为y。 

    这只发怒的奶牛想知道,一开始点燃哪个草堆,能使得最多的草堆被燃烧,请你计算出最多被烧掉的草堆数量。

    输入格式

    一行,一个整数n(1≤N≤100) 
    接下来n行,每行一个整数,分别代表n个草堆的位置,数字范围[0…1,000,000,000] 

    输出格式

    一行,一个整数,表示最多被烧掉的草堆数量 

    样例输入

    6
    8
    5
    6
    13
    3
    4

    样例输出

    5

    提示

    样例说明: 
    一开始点燃位于5的草堆,会使得4和6被引燃 
    4和6的引火半径为2,它们会将3和8引燃 
    3和8的引火半径为3,它们无法将13引燃


    来源  usaco 2016 January Contest Bronze Boss he翻译