<center>

1014: 火眼金睛

时间限制: 3 Sec  内存限制: 128 MB
提交: 88  解决: 24
</center>

题目描述

河海大学举办合唱比赛,比赛时,所有演唱人员需要从高到低依次排队.
为了确保演唱时的队形的整齐,导演不希望出现前后两名同学的身高差距太多,因此他希望在正式海选之前,就能知道某个参赛队在队员身高上是否能满足要求.
现在他给到你每个参赛队每个队员的身高,希望你能设计一个程序帮他计算出站好队形之后,前后两名同学身高差的最大值.

输入

第一行n,表示有n个数(N<=8000000)
第二行n个数,每个数< 2 31-1

输出

一个数,计算的结果

样例输入

7
7 4 1 1 6 5 9

样例输出

3

提示


火眼金睛,形容目光极其锐利,能以最快的速度找到差异.如果要达到火眼金睛的状态,可能需要更小(O(N))的时间复杂度.



 



---二次判定，数据被我减弱了，O(NlogN)也可以过了，大家加油OTZ

来源

河海ACM前辈：姜鹏



思路：

原本的题对时间复杂度要求很高。。必须要用O(n)的算法才能过，所以比赛时候没做出来，后来数据改松了。。虽然排个序就过了但是好不甘心，这里就当作原来没该数据之前做了。给定一个无序数组，找到数组中排序后相邻差最大的值。假定数组的值从MIN~MAX,则排序后相邻数的差临界情况就是等差排序的，因此maxgap >= (MAX-MIN)/(N-1)，此时可以对所有数字进行分组{1,2,..,maxgap}{maxgap+1,...2maxgap}...,将对应的数放在对应的组内即可。这样分组，由于组内的gap最大是maxgap-1因此最大的差肯定出现在组间，统计相邻组p q的q(min)-p(max),找最大值即为最大。


代码：

//From zyyyyy
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

const int N=8000010;
const int INF=((1<<30)-1)*2+1;
const double eps=1e-6;
int a[N],gmaxv[N],gminv[N];

int main()
{
	int n,i;
	int high=-INF,low=INF;
	scanf("%d",&n);
	for (i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		high=max(high,a[i]);
		low=min(low,a[i]);
	}
	double cd=1.0*(high-low)/(n-1);
	int ans=int(cd+0.5);
	for (i=1;i<=n;i++)
		gmaxv[i]=-INF,gminv[i]=INF;
	for (i=1;i<=n;i++)
	{
		if (a[i]==low) continue;
		int k=(a[i]-low)/cd;
		if (a[i]-low>k*cd) k++;
		gmaxv[k]=max(gmaxv[k],a[i]);
		gminv[k]=min(gminv[k],a[i]);
	}
	for (i=1;i<=n;i++)
	{
		if (gminv[i]==INF) continue;
		ans=max(ans,gminv[i]-low);
		low=gmaxv[i];
	}
	printf("%d\n",ans);
	return 0;
}