gap.cpp

最大间隙问题：给定n 个实数x , x , , xn 1 2 &#61516

#include"stdio.h"
#include<iostream>
#include<fstream>
using namespace std;


int main()
{

    freopen("input.txt","r",stdin);//从input.txt里面读入
    freopen("output.txt","w",stdout);//写入output.txt里面


	int i,n;
	scanf("%d",&n);

   double *array=new double[n];
   for( i=0;i<n;i++)
    scanf("%lf",&array[i]);

   
	double max,min;
	max=min=array[0];
    for(i=1;i<n;i++)
	{
		if(array[i]<min)
             min=array[i];
	    if(array[i]>max)
			max=array[i];
	}

	double intervallength=(max-min)/(n-1);

	int *flag=new int[n];//计算每个区间的数的个数；
	double *smallest=new double[n];//计算每个区间的最小值
	double *largest=new double[n];//计算每个区间的最大值

	//赋初值
	for(i=0;i<n;i++)
	{
		flag[i]=0;
		smallest[i]=max;
		largest[i]=min;
	}

	int interval=0;
	for(i=0;i<n;i++)
	{
	    interval=(int)((array[i]-min)/intervallength);
		flag[interval]++;
		if(array[i]<smallest[interval])
			smallest[interval]=array[i];
		if(array[i]>largest[interval])
			largest[interval]=array[i];
	}

	double tmp, gapmax=0;
	double beginpoint=largest[0];
	
	for(i=1;i<n;i++)
	{

	    if(flag[i]!=0)
		{
			tmp=smallest[i]-beginpoint;
			if(tmp>gapmax)
				gapmax=tmp;
			beginpoint=largest[i];
		
		}
	}

    cout<<gapmax;

	 
    delete[] array;
    delete[] flag; 
    delete[] smallest;
    delete[] largest;

	return 1;
}