问题描述:给定n个实数x1,x2,…,xn,求这n个实数在实轴上相邻2个数之间的最大差值,要求设计线性的时间算法。

初看题目,要想解决这个问题,最直观的解决方法就是将n个实数排序之后,线性寻找两两之间间隔的最大值。然而排序算法最好的复杂度是O(nlog(n)),所以这个方法可以排除了。

而解决这个问题的关键在于,我们可以意识到道一点:最大的间隔一定会大于等于平均的距离参考答案后意识到这一点整个问题的解决就简单多了。因为总共有n个实数点,抛除最大点与最小点以后,剩下的这n-2个点把整个最小值与最大值之间分出来了n-1个区间,因此我们在最大值与最小值之间平均分出n-1个区间,再把这n-2个点扔到这n-1个区间之中,保留每个区间中的最大值与最小值,因为间隔最大的区间一定比平均间隔大,所以最大的区间一定出现在至少两个相等的间隔之间。所以这样我们从头到尾搜索一遍之后我们就可以就可以找出最大的间隔点。

当然,到目前为止都没有提出鸽舍原理是个什么鬼。虽然不知道鸽舍原理我们也能把这个问题解决出来,但什么是鸽舍原理呢?

原理1:把n+1个元素分成n类,不管怎么分,则一定有一类中有2个或2个以上的元素。 原理2:把多于m×n个物体放到n个抽屉里,那么一定有一个抽屉里有m+1个或者m+1个以上的物体。

这是鸽舍原理的两个基本原理,我们只要稍微变通一下:在n个区间中放n-1个物体,那么,必定有一个区间为空。所以,最大间隔一定会横跨至少一个空区间,所以,有了鸽舍原理,就可以使得在从头到尾搜索的速度加快一些。

整个算法的实现如下:

#include<iostream>
#include<fstream>
using namespace std;
int main()
{
  const int MAXN=10000;
  const double MAXNUM=9999999999.9;
  int n;
  double nums[MAXN];
  ifstream ifs("input.txt");
  ofstream ofs("output.txt");
  double maxGap=0;
  ifs>>n;
  for(int i=0;i<n;i++)
  {
    ifs>>nums[i];
  }
  double mm=0,nn=MAXNUM,imm=0,inn=0,mGap[MAXN-1],nGap[MAXN-1];
  int cntGap[MAXN-1];
  for(int i=0;i<n;i++)
  {
    mGap[i]=0;
    nGap[i]=MAXNUM;
    cntGap[i]=0;
  }
  //maximum gap algorithm
  for(int i=0;i<n;i++)
  {
    if(nums[i]>mm)
    {
      mm=nums[i];
      imm=i;
    }
    if(nums[i]<nn)
    {
      nn=nums[i];
      inn=i;
    }
  }
  double meanGap=(mm-nn)/(n-1);
  for(int i=0;i<n;i++)
  {
    int gapIdx=int((nums[i]-nn)/meanGap);
    int addTime=0;
    if(i==imm||i==inn)
    {
      continue;
    }
    if(nums[i]>mGap[gapIdx])
    {
      mGap[gapIdx]=nums[i];
      addTime=1;
    }
    if(nums[i]<nGap[gapIdx])
    {
      nGap[gapIdx]=nums[i];
      addTime=1;
    }
    cntGap[gapIdx]+=addTime;
  }
  double mOld=nn,mGapAll=0;
  for(int i=0;i<n-1;i++)
  {
    if(cntGap[i]!=0)
    {
      if(nGap[i]-mOld>mGapAll)
      {
        mGapAll=nGap[i]-mOld;
      }
      mOld=mGap[i];
    }
  }
  if(mm-mOld>mGapAll) mGapAll=mm-mOld;
  ofs<<mGapAll;
  return 0;
}