愤怒的奶牛1

题目描述

奶牛贝里斯最近设计了款名叫“愤怒的奶牛”的游戏，在游戏中，可

以用一只愤怒的奶牛去引爆某个干草堆。当一个干草堆发生爆炸的时

候，会引爆一定范围内其他的干草堆爆炸，这样就会产生一系列的连 锁爆炸（假设干草堆里放了易燃易爆物品，小朋友们不要乱玩(⊙o⊙) 哦）。

有n个干草堆依次从左到右放在一条直线上，每个干草堆的位置（每个 位置保证不同）依次是x1，x2，x3...xn，如果奶牛把一个在位置x的 干草堆引爆了，那么这个干草堆的爆炸半径就是1，也就是说在距离这 个干草堆小于等于1范围内的其他干草堆都会引爆，这些被引爆的干草 堆的半径为2，然后被这些干草堆引爆的干草堆的爆炸半径是3，依次 增大，通俗的讲，就是如果某个干草堆是在时间t的时候被引爆的，那 么其爆炸半径就是t。

现在，请你来计算出最多可以引爆多少干草堆。

输入

第一行输入一个正整数n，表示干草堆的数量。

接下来n行，每行一个非负整数，表示每个干草堆的位置。

输出

输出只有一行一个整数，表示最多可以引爆的干草堆的数量

样例输入 复制

6

8

5

6

13

3

4

样例输出 复制

5

提示

样例中，最多只能引爆5个干草堆，愤怒的奶牛先把位于位置5的干草 堆引爆，导致位置6和位置4上的干草堆都引爆，然后导致位置3和位置 8上的干草堆都引爆，位置13上的干草堆由于距离太远，一直未能引爆 。

【数据说明】

1<=n<=100，所有干草堆的位置0<=xi<=1000000000。

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,i,a[110],r,j,ma,t;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(i=1;i<=n;i++)cin>>a[i];
	sort(a+1,a+n+1);
	for(t=1;t<=n;t++){
		i=t;r=1;
		while(1){
			for(j=1;j<=n;j++)
				if(a[j]>a[i]+r)
					break;
			if(j!=i-1)r++,i=j-1;
			else break;
		}
		i=t;r=1;
		while(1){
			for(j=1;j<=n;j++)
				if(a[j]<a[i]-r)
					break;
			if(j!=i+1)r++,i=j+1;
			else break;
		}
		ma=max(ma,i-t+1);
	}
	cout<<ma;
	return 0;
}