Gap.rar_文本文件_最大间隙问题

#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; }