计算机算法研究1-5的最大间隙问题

最大间隙问题研究

问题描述：

设存在n个实数x1,x2,...,xn，目标是计算这n个实数在实轴上相邻两个数值之间的最大间隔，并要求设计一种能够在线性时间内完成的算法。

初次接触到此问题时，首先想到的是采用排序方法，然而该方法的时间复杂度为O(nlogn)，显然高于O(n)的要求。

最终解决该问题所运用的是鸽巢原理，即当n-1个物品被分配到n个容器中时，必然存在至少一个容器为空。

在此题中，共有n个点，将这些点在直线上划分为n-1段。假设每段的长度为总长度除以(n-1)，然后将除去最左端和最右端的n-2个点分配到这n-1段中。根据原理可知，至少有一段不会包含任何点。最大的相邻间隔正是出现在这些空区间之间。因此，只需计算相邻两个区间的左边界与右边界之差的最大值即可得出结果。

 #include<bits/stdc++.h>

    
 using namespace std;
    
 #define inf 1<<30
    
 #define m 10000
    
 int n;
    
 double num[m],maxn=-inf,minn=inf;
    
 double maxx[m],mixx[m];
    
 double left;
    
 int book[m];
    
 int main()