#include<iostream.h>
#include<math.h>
#include<cstdlib>
#include<fstream.h>
template<class Type>
class MathProcess //用于做算法需要的比较复杂的数学运算
{
public:
MathProcess(){}
bool FindMaxAndMinValue(Type *p_NumList,int p_Len,Type& o_MaxValue,Type& o_MinValue)
{
if(p_Len<1)
{
o_MaxValue=-1;
o_MinValue=-1;
return false;
}
o_MaxValue=p_NumList[0];
o_MinValue=p_NumList[0];
for(int t_Index=1;t_Index<p_Len;t_Index++)
{
if(p_NumList[t_Index]>o_MaxValue)
o_MaxValue=p_NumList[t_Index];
if(p_NumList[t_Index]<o_MinValue)
o_MinValue=p_NumList[t_Index];
}
return true;
}
Type Average(Type p_Max,Type p_Min,Type p_DividedNum)
{
if(p_DividedNum>0)
return (p_Max-p_Min)/p_DividedNum;
else
return 0;
}
};
template<class Type>
class MaxGap //计算最大间隔的类
{
public:
MaxGap(){}
MaxGap(Type *p_NumList,int p_Len)
{
theList=p_NumList;
theLen=p_Len;
theAverageInterval=0;
theContainerNum=0;
}
~MaxGap()
{
delete []theDepMaxList;
delete []theDepMinList;
}
Type FindMaxGap()
{
Type t_MaxValue=0,t_MinValue=0,t_MaxGap=0;
MathProcess<Type> t_MathProcess;
if(t_MathProcess.FindMaxAndMinValue(theList,theLen,t_MaxValue,t_MinValue)==false)
return -1;
if((theAverageInterval=t_MathProcess.Average(t_MaxValue,t_MinValue,theLen-1))==0)
return 0;
t_MaxGap=theAverageInterval;
Type t_InitializedValue=t_MinValue-1;
//cout<<"MaxValue is:"<<t_MaxValue<<" "<<"MIn is"<<
// t_MinValue<<" "<<"AverageInterval is"<<theAverageInterval<<
// "t_Original is "<<t_OriginalValue<<endl;
theContainerNum=(int)(t_MathProcess.Average(t_MaxValue,t_MinValue,theAverageInterval))+1;
// cout<<"ContainerNum is"<<theContainerNum<<endl;
MakeDepartList(theContainerNum,t_InitializedValue); //区间数组初始化
for(int t_Index=0;t_Index<theLen;t_Index++)
{
int t_Location=(int)((theList[t_Index]-t_MinValue)/theAverageInterval);
if(theDepMaxList[t_Location]==t_InitializedValue)
{
theDepMaxList[t_Location]=theList[t_Index];
theDepMinList[t_Location]=theList[t_Index];
// cout<<"this Value is:"<<theList[t_Index]<<" location is"<<t_Location<<" now Max=True"<<endl;
}
else
{
if(theDepMaxList[t_Location]<theList[t_Index])
theDepMaxList[t_Location]=theList[t_Index];
if(theDepMinList[t_Location]>theList[t_Index])
theDepMinList[t_Location]=theList[t_Index];
//cout<<"this Value is:"<<theList[t_Index]<<" location is"<<t_Location<<" already Max=True,Min=true"<<endl;
}
}
Type t_CertainGap=0;
int t_PreValidIndex=-1; //记录前一个有效区间(即有序列中的数落在这个区间内)
for(int t_Index2=0;t_Index2<theContainerNum;t_Index2++)
{
if(theDepMaxList[t_Index2]>t_InitializedValue)
{
if(t_PreValidIndex==-1)
t_PreValidIndex=t_Index2;
else
{
t_CertainGap=theDepMinList[t_Index2]-
theDepMaxList[t_PreValidIndex];
t_PreValidIndex=t_Index2;
if(t_MaxGap<t_CertainGap)
t_MaxGap=t_CertainGap;
//cout<<"in the"<<t_Index2<<"turn: MaxGap="<<t_MaxGap<<endl;
}
}
}
return t_MaxGap;
}
private:
Type *theList;
int theLen;
Type theAverageInterval; //平均间隔
int theContainerNum; //分段数量
Type *theDepMaxList; //记录各分段区间的最大数值
Type *theDepMinList; //记录各分段区间的最小数值
void MakeDepartList(int p_Len,Type p_initializedValue)
{
//cout<<"original is "<<p_originalValue<<endl;
theDepMaxList=new Type[p_Len];
theDepMinList=new Type[p_Len];
for(int t_Index=0;t_Index<p_Len;t_Index++)
{
theDepMaxList[t_Index]=p_initializedValue;
theDepMinList[t_Index]=p_initializedValue;
//cout<<"theDepMInList["<<t_Index<<"]="<<theDepMinList[t_Index]<<endl;
}
}
};
int main()
{
int Len=0;
fstream fs,os;
fs.open("input.txt",ios::in);
fs>>Len;
//cout<<Len;
float *aList=new float[Len];
for(int i=0;i<=Len-1;i++)
{
fs>>aList[i];
}
fs.close();
os.open("output.txt",ios::out);
MaxGap<float> aMaxGap(aList,Len);
os<<aMaxGap.FindMaxGap();
os.close();
delete []aList;
return 0;
}
评论0