NanoApe Loves Sequence
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/131072 K (Java/Others)
Total Submission(s): 409 Accepted Submission(s): 189
NanoApe, the Retired Dog, has returned back to prepare for the National Higher Education Entrance Examination!In math class, NanoApe picked up sequences once again. He wrote down a sequence with numbers on the paper and then randomly deleted a number in the sequence. After that, he calculated the maximum absolute value of the difference of each two adjacent remained numbers, denoted as .
Now he wants to know the expected value of , if he deleted each number with equal probability.
The first line of the input contains an integer , denoting the number of test cases.In each test case, the first line of the input contains an integer , denoting the length of the original sequence.
The second line of the input contains integers , denoting the elements of the sequence.
For each test case, print a line with one integer, denoting the answer.In order to prevent using float number, you should print the answer multiplied by .
1
4
1 2 3 4
6
中文翻译：
退役狗 NanoApe 滚回去学文化课啦！ 在数学课上，NanoApe 心痒痒又玩起了数列。他在纸上随便写了一个长度为 nn 的数列，他又根据心情随便删了一个数，这样他得到了一个新的数列，然后他计算出了所有相邻两数的差的绝对值的最大值。 他当然知道这个最大值会随着他删了的数改变而改变，所以他想知道假如全部数被删除的概率是相等的话，差的绝对值的最大值的期望是多少。
我的思路：
求出初始时每两位数字之间差值的绝对值，排序，记录前三大的数据。然后用一个循环，如果删除第一位或者最后一位，它或许只能改变当前的最大值，同样求得相邻两个差值，如果是最大值，那当前最大值就是原来记录的第二大的数了，如果删除中间的数据，相邻两位之间差的绝对值可能大于最大值，此时最大值为相邻两位数字差的绝对值，否则判断他们是否改变最大值，若改变，判断差值是否大于第二大值，同理，若改变第二大值，则此时最大值为原来记录的第三大值，时间复杂度为O（n）。
AC代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
__int64 a[100500],dp[100500];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
long int N;
scanf("%ld",&N);
for(long int i=0; i<N; i++)
scanf("%I64d",a+i);
__int64 maxx=0,mainx=0,smax=0;
for(long int i=1; i<N; i++)
dp[i]=abs(a[i]-a[i-1]); //计算差值
sort(dp+1,dp+N); //排序
maxx=dp[N-1],mainx=dp[N-2],smax=dp[N-3]; //前三大差值
__int64 s=0;
for(long int i=0; i<N; i++)
{
if(i==0) //最左端
{
if(abs(a[1]-a[0])==maxx)s+=mainx;
else s+=maxx;
}
else if(i==N-1) //最右端
{
if(abs(a[N-1]-a[N-2])==maxx)s+=mainx;
else s+=maxx;
}
else
{
__int64 t=abs(a[i+1]-a[i-1]); //去掉该点之后新的差值
__int64 le=abs(a[i]-a[i-1]),ri=abs(a[i]-a[i+1]); //该点与左右相邻两点之间的差
if(le==maxx||ri==maxx) //如果会影响最大差值
{
if(t>=maxx)s+=t; //并且产生新的最大差
else
{
if(le==mainx||ri==mainx) //如果影响最大差的情况下还影响了第二大的差
{
if(t>=mainx)s+=t; //产生新的最大差
else s+=smax; //否则加上原来第三大差值 因为第一二大差已经被破坏
}
else //如果不影响第二大差值
{
if(t>=mainx)s+=t; //但破坏最大差的情况下大于第二大差值
else s+=mainx; //不破坏第二大差值
}
}
}
else if(t>maxx)s+=t; //如果产生了新的最大差值
else s+=maxx; //没有影响到此时的最大差值
}
}
printf("%I64d\n",s);
}
return 0;
}
