最大间隙问题

问题描述：

最大间隙问题：给定n 个实数x1, x2 ,…, xn，求这n 个数在实轴上相邻2 个数之间的最大差值。假设对任何实数的下取整函数耗O(1)，设计解最大间隙问题的线性时间算法。

对于给定的n 个实数x1,x2,…,xn，编程计算它们的最大间隙
input.txt
5
2.3 3.1 7.5 1.5 6.3

output.txt
3.2

思路：

线性时间求解，所以不能排序来做。
鸽舍原理了解一下
鸽舍原理：
也称“抽屉原理”或利克雷原则，它是一个重要而又基本的数学原理，应用它可以解决各种有趣的问题，并且常常能够得到令人惊奇的结果，许多看起来相当复杂，甚至无从下手的问题，利用它能很容易得到解决。
原理1：把n+1个元素分成n类，不管怎么分，则一定有一类中有2个或2个以上的元素。
原理2：把多于m×n个物体放到n个抽屉里，那么一定有一个抽屉里有m+1个或者m+1个以
上的物体。
原理2-1：把m个元素任意放入n（n<m）个集合，则一定有一个集合呈至少要有k个元素。
其中 k= [m/n]([]表示向上取整）。
（抽屉原理的一般含义为:“如果每个抽屉代表一个集合,每一个苹果就可以代表一个元素,假如有 n+1或多于n+1个元素放到n个集合中去,其中必定至少有一个集合里至少有两个元素。” ）

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
typedef long long LL;
const int maxn = 100+5;
int n;
double x[maxn], low[maxn], high[maxn];
int cnt[maxn];//桶中的元素个数计数

//寻找最小值的下标
int find_min_pos(){
	double t = x[1];
	int k = 1;
	for(int i = 2; i <= n; ++i) if(t > x[i]) t = x[k = i];
	return k;
}
int find_max_pos(){
	double t = x[1];
	int k = 1;
	for(int i = 2; i <= n; ++i) if(t < x[i]) t = x[k = i];
	return k;
}

//鸽舍原理求解最大间隔问题 
double maxgap(){
	
	int min_pos = find_min_pos(), max_pos = find_max_pos();
	double minx = x[min_pos], maxx = x[max_pos];
	if(n <= 2){
		return maxx - minx;
	}
	
	/*
	[minx, maxx]由n-2个等间隔点分成n-1个桶, 每个桶用low[i]和high[i]
	分别来表示分配给桶i的cnt[i]个数中的最小值和最大值
	*/
	//桶初始化
	for(int i = 1; i <= n-1; ++i){
		cnt[i] = 0;
		low[i] = maxx;
		high[i] = minx;
	}
	//将n个数装入n-1个桶
	for(int i = 1; i <= n; ++i){
		int bucket = int((n-1) * (x[i] - minx) / (maxx - minx)) + 1;//给x[i]分配桶 
		++cnt[bucket];
		if(x[i] < low[bucket]) low[bucket] = x[i];
		if(x[i] > high[bucket]) high[bucket] = x[i];
	}
	/*
	此时, 除minx, maxx外, n-2个数被装入了n-1个桶, 根据鸽舍原理, 必定有一个桶是空的
	这也说明最大间隙不可能存在于桶内
	*/
	double ans = 0, left = high[1];
	for(int i = 2; i <= n-1; ++i){
		if(cnt[i] == 0) continue;
		double gap = low[i] - left;
		if(gap > ans)
			ans = gap;
		left = high[i];
	}
	return ans;
}

int main()
{
	freopen("in.txt","r",stdin);
	
	while(scanf("%d",&n) == 1&&n){
		for(int i = 1; i <= n; ++i) scanf("%lf",&x[i]);
		double ans = maxgap();
		printf("%lf\n", ans);
	}
	fclose(stdin);
	return 0;
}