3899: 愤怒的小鸟
内存限制:128 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:27
解决:6
题目描述
angry.in/angry.out
小W设计出了一个热门电玩游戏“愤怒的小鸟”。玩家用弹弓弹射一只小鸟,目标是前方一排 位于数字线上不同点的爆炸珠; 小鸟撞击爆炸珠后能产生足够的能量使爆炸珠爆炸, 爆炸 珠爆炸后又可能造成连锁反应,导致附近的爆炸珠爆炸。任务是用一只小鸟轰击爆炸珠,让爆 炸珠连锁反应,并且尽可能多的引爆爆炸珠。
有 n 个位于不同整数位置 X1,X2,... Xn 的爆炸珠。一开始如果小鸟撞击位于 x 位置上 的爆炸珠,那么 x 位置上的爆炸珠就会被引爆,并且这个爆炸珠爆炸的“爆炸半径”为 1, 这意味着任何其他爆炸珠在一个单位的距离内也被引爆。然后这些相邻的珠子自身爆炸同事 也会引爆它边上的爆炸珠,每个爆炸半径都为 2,所以这些爆炸可能会将另外相距最多 2 个 距离的未爆炸的爆炸珠继续引爆。在下一个时间步骤中,这些珠子也会以引爆半径 3 来引爆 其它爆炸珠。每增加一次连锁爆炸,那么引爆半径就增加 1.
你的任务就是确定愤怒的小鸟应该撞击哪个爆炸珠,最后能引爆最多的爆炸珠。
小W设计出了一个热门电玩游戏“愤怒的小鸟”。玩家用弹弓弹射一只小鸟,目标是前方一排 位于数字线上不同点的爆炸珠; 小鸟撞击爆炸珠后能产生足够的能量使爆炸珠爆炸, 爆炸 珠爆炸后又可能造成连锁反应,导致附近的爆炸珠爆炸。任务是用一只小鸟轰击爆炸珠,让爆 炸珠连锁反应,并且尽可能多的引爆爆炸珠。
有 n 个位于不同整数位置 X1,X2,... Xn 的爆炸珠。一开始如果小鸟撞击位于 x 位置上 的爆炸珠,那么 x 位置上的爆炸珠就会被引爆,并且这个爆炸珠爆炸的“爆炸半径”为 1, 这意味着任何其他爆炸珠在一个单位的距离内也被引爆。然后这些相邻的珠子自身爆炸同事 也会引爆它边上的爆炸珠,每个爆炸半径都为 2,所以这些爆炸可能会将另外相距最多 2 个 距离的未爆炸的爆炸珠继续引爆。在下一个时间步骤中,这些珠子也会以引爆半径 3 来引爆 其它爆炸珠。每增加一次连锁爆炸,那么引爆半径就增加 1.
你的任务就是确定愤怒的小鸟应该撞击哪个爆炸珠,最后能引爆最多的爆炸珠。
【样例说明】
愤怒的小鸟撞击 5 号爆炸珠,接着将导致 4 号和 6 号的珠子爆炸,再接着引爆半径 2。这些
爆炸反过来又导致 3 号和 8 号的珠子爆炸,但这些最后的爆炸力不够强大,无法到达 13
号珠子。
输入
第一行一个整数 n 表示有多少爆炸珠(1 ≤ n≤100)。
接下来 n 行每行一个整数,表示爆炸珠的位置 x。(0≤x≤1000000000)
输出
一行,最后能引爆最多的爆炸珠的个数。
样例输入 复制
6
8
5
6
13
3
4
样例输出 复制
5