编程极差

① ACM 数列极差问题

//已AC啦，兄弟，别嫌长，大数模板，很实用哦！

/*****************************************************************************
无符号大整数类，包括了*和+法，类可以用小整数或者字符串输入，储存方式为:下标大的位储存高位
字符串输入时，必须手动去除前面多余的0
加法函数和乘法函数中，前2个参数为输入，最后个返回，参数中，前两个可以相同，但是最后个不能和前面的重复
减法函数中，被减数a必须大于减数b，返回到a中，要算c=a-b可以用Cpy,Sub两个函数合用
******************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include <algorithm>
#include <iostream>
using namespace std;

const int OneNode = 1000000 ;//一位里不能超过OneNode
const int NodeLen = 6 ;//一位储存NodeLen位，和OneNode必须同时更改,输出部分格式必须跟随这里!!!
const int Numtmax = 4005 ;//储存位数限制，真实位数为Numtmax*6
struct BigNum
{
unsigned num[Numtmax] ;//高位 对 下标大位
unsigned numlen ;
void set(unsigned sm=0){ num[0] = sm ; numlen = 1; }//sm<OneNode
void set(char *string , int strlen)
{
numlen = (strlen-1) / NodeLen + 1 ;
memset (num , 0 , sizeof(unsigned)*numlen );
int temp , i ;
for( i=strlen-1 ; i>=0 ; i-- )
{
temp = i / NodeLen ;
num[temp] = num[temp]*10 + string[strlen-1-i]-'0' ;
}
}
void print()
{
printf("%d",num[numlen-1]);
int i = numlen-1;
while( i )
{
i--;
printf("%06d",num[i]);
}
printf("\n");
}
};

void Add(BigNum &a,BigNum &b,BigNum &c) // a+b ->c
{
unsigned lentmax = a.numlen>b.numlen?a.numlen:b.numlen;
c.numlen = lentmax;
unsigned i,carry=0;
for ( i=0 ; i<lentmax ; i++ )
{
c.num[i] = carry ;
if( a.numlen > i )
c.num[i]+= a.num[i];
if( b.numlen > i )
c.num[i]+= b.num[i];
carry = c.num[i] / OneNode ;
c.num[i] %= OneNode ;
}
if ( carry )
{
c.num[i] = carry ;
c.numlen ++;
}
}

void Mul(BigNum &a,BigNum &b,BigNum &c) // a*b ->c
{
unsigned carry = 0 , lentmax = a.numlen+b.numlen-1 ,i,j ;
unsigned __int64 temp ;
c.numlen = lentmax;
for ( i=0 ; i<lentmax ; i++ )
{
temp = carry ;
for ( j=0 ; j<a.numlen ; j++ )
{
if ( i<j )
break;
if ( i-j >= b.numlen )
{
j = i-b.numlen ;
continue;
}
temp += (unsigned __int64)a.num[j] * b.num[i-j] ;
}
carry = temp / OneNode ;
c.num[i] = temp % OneNode ;
}
while(carry)
{
c.num[c.numlen++] = carry % OneNode ;
carry/=OneNode;
}
while(c.numlen>1&&!c.num[c.numlen-1])
c.numlen--;
}

int Cmp(BigNum &a,BigNum &b) //a>b --> 1 , < --> -1 ,== --> 0
{
if( a.numlen>b.numlen )
return 1;
if( a.numlen<b.numlen )
return -1;
int len = a.numlen ;
while(len)
{
len --;
if(a.num[len]>b.num[len])return 1;
if(a.num[len]<b.num[len])return -1;
}
return 0;
}

void Cpy(BigNum &a , BigNum &b) //b-->a
{
a.numlen=b.numlen;
memcpy(a.num,b.num,sizeof(unsigned)*b.numlen);
}

void Sub( BigNum &a , BigNum b ) //a-b -> a , a>=b
{
unsigned i = 0;
unsigned carry = 0 ;
for ( i=0 ; i<b.numlen ; i++ )
{
a.num[i] = a.num[i]-carry-b.num[i];
if(a.num[i]>OneNode) //有进位(由于相减如果小于0会向上溢出)
{
a.num[i] += OneNode ;
carry = 1;
}
else carry = 0;
}
while(carry)
{
if(a.num[i])
{
a.num[i] --;
carry = 0;
}
else
{
a.num[i] = OneNode-1;
i++;
}
}
while(a.num[a.numlen-1]==0 && a.numlen!=1)
{
a.numlen --;
}
}
void Div(BigNum &a,int b,int &l) // a/=b -> 余数l
{
int carry=0;
int i;
for(i=a.numlen-1;i>=0;i--)
{
a.num[i]+=carry*OneNode;
carry=a.num[i]%b;
a.num[i]/=b;
}
if(a.numlen>1&&!a.num[a.numlen-1])a.numlen--;
l=carry;
}

/********以上是模板部分，送给你啦**********/

int n;
int a[2010],b[2010];
BigNum c[2010],t,tmax,tmin,ans,one;

bool cmp (const int a, const int b)
{
return a > b;
}

int main()
{
one.set(1);
while(scanf("%d",&n)!=EOF)
{
int i,j;
for(i=0;i<n;++i)
{
scanf("%d",&a[i]);
b[i]=a[i];
}
sort(a,a+n); //计算tmax
for(i=0;i<n;++i)
{
c[i].set(a[i]);
}
for(i=1;i<n;i++)
{
Mul(c[i-1],c[i],c[n]); //c[n]=c[i-1]*c[i]
Add(c[n],one,t); //t=c[n]+1;
for(j=i+1;j<n;++j)
{
if(Cmp(t,c[j])<=0) //t<=c[j]
{
break;
}
else
{
Cpy(c[j-1],c[j]); //c[j-1]=c[j]
}
}
Cpy(c[j-1],t);
}
Cpy(tmax,c[n-1]);

sort(b,b+n,cmp); //计算tmin
for(i=0;i<n;++i)
{
c[i].set(b[i]);
}
for(i=1;i<n;i++)
{
Mul(c[i-1],c[i],c[n]);
Add(c[n],one,t);
for(j=i+1;j<n;++j)
{
if(Cmp(t,c[j])>=0) //t<=c[j]
{
break;
}
else
{
Cpy(c[j-1],c[j]);
}
}
Cpy(c[j-1],t);
}
Cpy(tmin,c[n-1]);

Sub(tmax,tmin); //tmax=tmax-tmin;
int cnt,v;
cnt=0;
v=tmax.num[tmax.numlen-1];
do
{
cnt++;
v/=10;
}while(v);
if(tmax.numlen-2>=0) cnt+=(tmax.numlen-1)*6;
printf("%d\n",cnt);
tmax.print();
}

return 0;
}