gap.cpp

算法实现题1-5 最大间隙问题 &laquo 问题描述： 最大间隙问题：给定n 个实数x , , xn 1 2 &#61516

#include<iostream.h>
#include<fstream.h>
#include<stdlib.h>
#include<time.h> 

struct Node
{
	float secMin;
	float secMax;
	char flag;
};

void main()
{
	
	ifstream istrm;
	ofstream ostrm;

	istrm.open("input.txt");
	ostrm.open("output.txt");
	int N;            //问题规模
	istrm>>N;
	float *a=new float[N];

	for(int i=0;i<N;i++)
		istrm>>a[i];

	float min=a[0],max=a[0];
	for(i=1;i<N;i++)
	{
	   if(a[i]>max)max=a[i];
	   if(a[i]<min)min=a[i];
	}
	
	if(min==max)
	   ostrm<<0<<endl;
	else
    {
	   float l=(max-min)/(N-1);
	   float startMin,startMax,maxDistance=l;
	   int temp;
	   struct Node *p=new struct Node[N-1];
	   for(i=0;i<N-1;i++)
		   p[i].flag=0;
	   for(i=0;i<N;i++)
	   {
		    temp=int((a[i]-min)/l);
			if(!p[temp].flag)
			{
				p[temp].secMin=p[temp].secMax=a[i];
				p[temp].flag=1;
			}
			else
			{
				if(a[i]>p[temp].secMax)
					p[temp].secMax=a[i];
				if(a[i]<p[temp].secMin)
					p[temp].secMin=a[i];
			}
	   }

	   for(i=0;i<N-1;i++)
	   {
		   if(p[i].flag)
		   {
			   startMax=p[i].secMax;
			   break;
		   }
	   }
	   for(i++;i<N-1;i++)
	   {
		   if(p[i].flag)
		   {
			   startMin=p[i].secMin;
			   if(startMin-startMax>maxDistance)
					maxDistance=startMin-startMax;
			   startMax=p[i].secMax;
		   }		   
	   }
	   ostrm<<maxDistance<<endl;
	   delete []p;
    }
	delete []a;
}