HDU 5805:NanoApe Loves Sequence

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


Problem Description

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.

 

Input

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.

 

Output

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 .

 

Sample Input
1
4
1 2 3 4

 

Sample Output

 

中文翻译:

  退役狗 NanoApe 滚回去学文化课啦! 在数学课上,NanoApe 心痒痒又玩起了数列。他在纸上随便写了一个长度为 nn 的数列,他又根据心情随便删了一个数,这样他得到了一个新的数列,然后他计算出了所有相邻两数的差的绝对值的最大值。 他当然知道这个最大值会随着他删了的数改变而改变,所以他想知道假如全部数被删除的概率是相等的话,差的绝对值的最大值的期望是多少。

 

  在输出描述中有说明,为了防止精度误差,给期望值乘以n得到最终结果,这样的话整个题目就是算去除每一位数字之后的最大值之和啦!

  不能考虑暴力的思想哦,因为数据范围都是很大的。

 

我的思路:

  求出初始时每两位数字之间差值的绝对值,排序,记录前三大的数据。然后用一个循环,如果删除第一位或者最后一位,它或许只能改变当前的最大值,同样求得相邻两个差值,如果是最大值,那当前最大值就是原来记录的第二大的数了,如果删除中间的数据,相邻两位之间差的绝对值可能大于最大值,此时最大值为相邻两位数字差的绝对值,否则判断他们是否改变最大值,若改变,判断差值是否大于第二大值,同理,若改变第二大值,则此时最大值为原来记录的第三大值,时间复杂度为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;
}