Hdu-5805-nanoape loves sequence (thinking questions)

NanoApe Loves Sequence

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 262144/131072 K (Java/Others)
Total Submission(s): 1087    Accepted Submission(s): 448

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  n 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  F.

Now he wants to know the expected value of  F, if he deleted each number with equal probability.

 

Input

The first line of the input contains an integer T, denoting the number of test cases.

In each test case, the first line of the input contains an integer n, denoting the length of the original sequence.

The second line of the input contains n integers A1,A2,...,An,  denoting the elements of the sequence.

1≤T≤10, 3≤n≤100000, 1≤Ai≤109

 

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 n.

 

Sample Input

  
   

    
   1
4
1 2 3 4
  
   

 

Sample Output

  
   

    
   6
  
   

 

Source

BestCoder Round #86

   This question is called thinking question , Just read the meaning of the question ： Enter an array , After randomly deleting a number , Record the maximum absolute value of two adjacent numbers in the remaining new array as F. Now delete one of the numbers with the same probability , seek F The expectation of .

 

   When the probability is equal , expect = probability （1/n）* The sum of the , But pay attention to the last sentence , Output the expected answer times n, It means to sum up .

  

Code

/**
* @Date:   2016-07-21 10-41-21
* @Project: ACM
* @Last modified time: 2016-08-08 01-53-22
*/



#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define maxn 100005


int n, m;
long long sum;
long long L[maxn], R[maxn];
long long a[100004];


int main () {
    int t;
    scanf ("%d", &t);
    while (t--) {
        scanf ("%d", &n);
        for (int i = 1; i <= n; i++) scanf ("%lld", &a[i]);
        sum = 0;


        //printf("==%d==%d\n",L[1],R[n]);
        L[1] = -1, R[n] = -1;// The left and right ends are assigned small enough initial values 
        /**
         *  Preprocessing , Based on the number to be deleted , Pretreat both sides 
         */
        for (int i = 2; i <= n; i++) { // Preprocess to the left , Make the absolute value of the maximum difference on the left side L[i]
            L[i] = max (L[i-1], abs (a[i]-a[i-1])); 
        } 
        for (int i = n-1; i >= 1; i--) { // Pretreatment to the right , Make the absolute value of the maximum difference on the right side R[i]
            R[i] = max (R[i+1], abs (a[i]-a[i+1]));
        }
        /**
         *  Special treatment is required when deleting numbers at both ends , Get the maximum 
         *  When deleting the middle number , Consider the absolute value of the difference between the number before deletion and the left and right adjacent numbers , And a new difference is generated . Need to discuss and deal with 
         */
        for (int i = 1; i <= n; i++) {
            if (i == 1) sum += R[2]; // When the first number is deleted , Think to the right , here R[2] Is the absolute value of the maximum difference 
            else if (i == n) sum += L[n-1];// When the last number is deleted , Think to the left , here L[n-1] Is the absolute value of the maximum difference 
            // When deleting the middle number , First, compare the absolute value of the difference between the number before deletion and the numbers on the left and right sides , Take the larger value , Then compare with the new absolute value of the difference , Taking the maximum 
            else sum += max (max (L[i-1], R[i+1]), abs (a[i+1]-a[i-1]));
        }
        printf ("%lld\n", sum);// Sum up , At sight *n Result 
    }
    return 0;
}