【HDU】5805 - NanoApe Loves Sequence（模拟）

退役狗 NanoApe 滚回去学文化课啦！

在数学课上，NanoApe 心痒痒又玩起了数列。他在纸上随便写了一个长度为 nn 的数列，他又根据心情随便删了一个数，这样他得到了一个新的数列，然后他计算出了所有相邻两数的差的绝对值的最大值。

他当然知道这个最大值会随着他删了的数改变而改变，所以他想知道假如全部数被删除的概率是相等的话，差的绝对值的最大值的期望是多少。

第一行为一个正整数 TT，表示数据组数。

每组数据的第一行为一个整数 nn。

第二行为 nn 个整数 A_iA​i​​，表示这个数列。

1 \le T \le 10,~3 \le n \le 100000,~1 \le A_i \le 10^91≤T≤10, 3≤n≤100000, 1≤A​i​​≤10​9​​

对于每组数据输出一行一个数表示答案。

为防止精度误差，你需要输出答案乘上 nn 后的值。

1
4
1 2 3 4

6

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define INF 0x3f3f3f3f
#define CLR(a,b) memset(a,b,sizeof(a))
struct node
{
    int v;
    int pos;
}max1,max2,max3,tt;
int main()
{
    int u;
    int n;
    __int64 ans;
    int num[100000+11];
    scanf ("%d",&u);
    while (u--)
    {
        scanf ("%d",&n);
        ans = 0;
        scanf ("%d",&num[1]);
        max1.v = 0;
        max2.v = 0;
        max3.v = 0;
        for (int i = 2 ; i <= n ; i++)
        {
            scanf ("%d",&num[i]);
            if (abs(num[i] - num[i-1]) > max1.v)
            {
                max3 = max2;
                max2 = max1;
                max1.v = abs(num[i] - num[i-1]);
                max1.pos = i;
            }
            else if (abs(num[i] - num[i-1]) > max2.v)
            {
                max3 = max2;
                max2.v = abs(num[i] - num[i-1]);
                max2.pos = i;
            }
            else if (abs(num[i] - num[i-1]) > max3.v)
            {
                max3.v = abs(num[i] - num[i-1]);
                max3.pos = i;
            }
        }
        if (max1.pos == 2)
            ans += max2.v;
        else
            ans += max1.v;
        if (max1.pos == n)
            ans += max2.v;
        else
            ans += max1.v;
        for (int i = 2 ; i < n ; i++)
        {
            if (max1.pos != i && max1.pos - 1 != i)
                ans += max (max1.v , abs(num[i-1] - num[i+1]));
            else
            {
                if (max1.pos == i+1)
                {
                    if (max2.pos == i)
                    {
                        ans += max (max3.v , abs(num[i-1] - num[i+1]));
                    }
                    else
                    {
                        ans += max (max2.v , abs(num[i-1] - num[i+1]));
                    }
                }
                else
                {
                    if (max2.pos == max1.pos + 1)
                    {
                        ans += max (max3.v , abs(num[i-1] - num[i+1]));
                    }
                    else
                    {
                        ans += max (max2.v , abs(num[i-1] - num[i+1]));
                    }
                }
            }
        }
        printf ("%I64d\n",ans);
    }
    return 0;
}