问题描述
给定n个实数x1, x2, x3, … , xn, 求这n个数在实轴上相邻2个数之间的最大间隔。假设对任何实数取整耗时O(1), 设计解最大间隙问题的线性时间算法。
算法设计
对于给定的n个实数x1, x2, x3, … , xn, 计算它们的最大间隙。
数据输入
输入数据由文件名为input.txt的文本文件提供,文件的第1行有1一个正整数n, 接下来1行中有n个实数x1, x2, x3, … , xn。
数据输出
将找到的最大间隔输出到文件output.txt
样例
输入:
5
2.3 3.1 7.5 1.5 6.3
输出:
3.2
算法实现分析
本问题可以运用鸽巢原理进行解答。其具体实现步骤如下:
- 找出n个实数中的最大值n_max 和 最小值n_min
- 申请n+1个盘子,并记录每一个盘子中的元素个数、上下界
- 将[n_min, n_max]划分成n-1个等长区间,第一个盘子只放最小值,最后一个盘子只放最大值,剩余n-1个盘子用来存放n-2个数。很明显,必然至少有一个盘子没有存放任何数。因此,最大间隔存在于空盘子的两侧。
- 线性查找出最大间隔。
实现代码
#include <iostream>
#include <fstream>
#include <cstring>
#include <math.h>
using namespace std;
#de