solution.md

# 灵能传输


**题目背景**

在游戏《星际争霸 II》中，高阶圣堂武士作为星灵的重要 AOE 单位，在游戏的中后期发挥着重要的作用，其技能”灵能风暴“可以消耗大量的灵能对一片区域内的敌军造成毁灭性的伤害。经常用于对抗人类的生化部队和虫族的刺蛇飞龙等低血量单位。

**问题描述**

你控制着 n 名高阶圣堂武士，方便起见标为 1,2,··· ,n。每名高阶圣堂武士需要一定的灵能来战斗，每个人有一个灵能值$a_i$表示其拥有的灵能的多少（$a_i$非负表示这名高阶圣堂武士比在最佳状态下多余了$a_i$点灵能，$a_i$为负则表示这名高阶圣堂武士还需要$-a_i$点灵能才能到达最佳战斗状态） 。现在系统赋予了你的高阶圣堂武士一个能力，传递灵能，每次你可以选择一个$ i ∈ [2,n − 1]$，若$a_i ≥ 0 $则其两旁的高阶圣堂武士，也就是$ i − 1、i + 1 $这两名高阶圣堂武士会从i 这名高阶圣堂武士这里各抽取$ a_i $点灵能；若$ a_i < 0 $则其两旁的高阶圣堂武士，也就是$ i−1,i+1 $这两名高阶圣堂武士会给 i 这名高阶圣堂武士$ −a_i $点灵能。形式化来讲就是$ a_{i-1} + = a_i ,a_{i+1} + = a_i ,a_i − = 2a_i $。  

灵能是非常高效的作战工具，同时也非常危险且不稳定，一位高阶圣堂武士拥有的灵能过多或者过少都不好，定义一组高阶圣堂武士的不稳定度为$max^n_{i=1} |a_i|$，请你通过不限次数的传递灵能操作使得你控制的这一组高阶圣堂武士的不稳定度最小。

**输入格式**

本题包含多组询问。输入的第一行包含一个正整数 T 表示询问组数。  

接下来依次输入每一组询问。  

每组询问的第一行包含一个正整数 n，表示高阶圣堂武士的数量。  

接下来一行包含 n 个数 $a_1 ,a_2 ,··· ,a_n $。  

**输出格式**

输出 T 行。每行一个整数依次表示每组询问的答案。

**样例输入**

```
3
3
5 -2 3
4
0 0 0 0
3
1 2 3
```

**样例输出**

```
3
0
3
```

**样例说明**

```
对于第一组询问：
对 2 号高阶圣堂武士进行传输操作后 a 1 = 3，a 2 = 2，a 3 = 1。答案为 3。
对于第二组询问：
这一组高阶圣堂武士拥有的灵能都正好可以让他们达到最佳战斗状态。
```

**样例输入**

```
3
4
-1 -2 -3 7
4
2 3 4 -8
5
-1 -1 6 -1 -1
```

**样例输出**

```
5
7
4
```

以下选项<span style="color:red">错误</span>的是？

## aop

### before

```c
#include <bits/stdc++.h>
using namespace std;
```

### after

```c

```

## 答案

```c
typedef long long ll;
#define int ll
#define rep(i, a, n) for (int i = a; i < (int)n; i++)
#define per(i, a, n) for (int i = (int)n - 1; i >= a; i--)
const int maxn = 3e5 + 10;
inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = (x << 3) + (x << 1) + ch - 48;
        ch = getchar();
    }
    return x * f;
}
int s[maxn], a[maxn];
bool vis[maxn];
inline void cf()
{
    int t = read();
    while (t--)
    {
        int n = read();
        s[0] = 0;
        rep(i, 1, n + 1)
        {
            int x = read();
            s[i] = s[i + 1] + x;
        }
        int s0 = 0, sn = s[n];
        if (s0 > sn)
            swap(s0, sn);
        sort(s, s + n + 1);
        rep(i, 0, n + 1) if (s[i] == s0)
        {
            s0 = i;
            break;
        }
        per(i, 0, n + 1) if (s[i] == sn)
        {
            sn = i;
            break;
        }
        int l = 0, r = n;
        rep(i, 0, n + 1) vis[i] = 0;
        for (int i = s0; i >= 0; i -= 2)
            a[l++] = s[i], vis[i] = 1;
        for (int i = sn; i <= n; i += 2)
            a[r--] = s[i], vis[i] = 1;
        rep(i, 0, n + 1) if (!vis[i]) a[l++] = s[i];
        int ans = 0;
        rep(i, 1, n + 1) ans = max(ans, abs(a[i] - a[i - 1]));
        printf("%lld\n", ans);
    }
    return;
}
signed main()
{
    cf();
    return 0;
}
```

## 选项

### A

```c
#define ll long long
const int N = 3e5;
ll a[N], s[N];
bool vis[N];
int n;
int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        memset(vis, 0, sizeof(vis));
        scanf("%d", &n);
        s[0] = 0;
        for (int i = 1; i <= n; ++i)
        {
            scanf("%lld", &s[i]);
            s[i] += s[i - 1];
        }
        ll s0 = 0, sn = s[n];
        if (s0 > sn)
            swap(s0, sn);
        sort(s, s + n + 1);
        int l = 0, r = n;
        for (int i = lower_bound(s, s + n + 1, s0) - s; i >= 0; i -= 2)
        {
            a[l++] = s[i], vis[i] = 1;
        }
        for (int i = lower_bound(s, s + n + 1, sn) - s; i <= n; i += 2)
        {
            a[r--] = s[i], vis[i] = 1;
        }
        for (int i = 0; i <= n; ++i)
        {
            if (!vis[i])
                a[l++] = s[i];
        }
        ll res = 0;
        for (int i = 1; i <= n; ++i)
            res = max(res, abs(a[i] - a[i - 1]));
        printf("%lld\n", res);
    }
    return 0;
}
```

### B

```c
const int MAXN = 300010;
int nums[MAXN];

bool judgeYi(int a, int b)
{
    return a > 0 && b < 0 || a < 0 && b > 0;
}

int main()
{
    int T, n;
    cin >> T;
    while (T--)
    {
        cin >> n;

        bool hasNe = false, hasPo = false;
        int res = 0;
        for (int i = 0; i < n; i++)
        {
            scanf("%d", &nums[i]);
            if (nums[i] < 0)
            {
                hasNe = true;
            }
            else if (nums[i] > 0)
            {
                hasPo = true;
            }
        }

        if (hasNe && hasPo)
        {
            bool canNext;
            do
            {
                canNext = false;
                for (int i = 1; i < n - 1; i++)
                {

                    if (judgeYi(nums[i], nums[i - 1]) || judgeYi(nums[i], nums[i + 1]))
                    {
                        if (nums[i] > 0)
                        {

                            if (judgeYi(nums[i - 1], nums[i + 1]))
                            {
                                if ((nums[i - 1] > 0 && abs(nums[i + 1]) > nums[i - 1] + nums[i]) ||
                                    (nums[i + 1] > 0 && abs(nums[i - 1]) > nums[i + 1] + nums[i]))
                                {
                                    nums[i + 1] += nums[i];
                                    nums[i - 1] += nums[i];
                                    nums[i] = -nums[i];
                                    canNext = true;
                                }
                            }
                            else
                            {
                                if (abs(nums[i - 1]) > nums[i] || abs(nums[i + 1]) > nums[i])
                                {
                                    nums[i + 1] += nums[i];
                                    nums[i - 1] += nums[i];
                                    nums[i] = -nums[i];
                                    canNext = true;
                                }
                            }
                        }
                        else if (nums[i] < 0)
                        {

                            if (judgeYi(nums[i - 1], nums[i + 1]))
                            {
                                if ((nums[i - 1] > 0 && nums[i - 1] > abs(nums[i + 1] + nums[i])) ||
                                    (nums[i + 1] > 0 && nums[i + 1] > abs(nums[i - 1] + nums[i])))
                                {
                                    nums[i + 1] += nums[i];
                                    nums[i - 1] += nums[i];
                                    nums[i] = -nums[i];
                                    canNext = true;
                                }
                            }
                            else
                            {
                                if (nums[i - 1] > abs(nums[i]) || nums[i + 1] > abs(nums[i]))
                                {
                                    nums[i + 1] += nums[i];
                                    nums[i - 1] += nums[i];
                                    nums[i] = -nums[i];
                                    canNext = true;
                                }
                            }
                        }
                    }
                }
            } while (canNext);
        }
        int t;

        for (int i = 0; i < n; i++)
        {
            res = max(res, abs(nums[i]));
        }
        cout << res << endl;
    }

    return 0;
}
```

### C

```c
typedef long long LL;
const int INF = 0x3f3f3f3f;
const double Pi = acos(-1);
namespace
{
    template <typename T>
    inline void read(T &x)
    {
        x = 0;
        T f = 1;
        char s = getchar();
        for (; !isdigit(s); s = getchar())
            if (s == '-')
                f = -1;
        for (; isdigit(s); s = getchar())
            x = (x << 3) + (x << 1) + (s ^ 48);
        x *= f;
    }
}
#define fio                      \
    ios::sync_with_stdio(false); \
    cin.tie(0);                  \
    cout.tie(0);
#define _for(n, m, i) for (register int i = (n); i < (m); ++i)
#define _rep(n, m, i) for (register int i = (n); i <= (m); ++i)
#define _srep(n, m, i) for (register int i = (n); i >= (m); i--)
#define _sfor(n, m, i) for (register int i = (n); i > (m); i--)
#define lson rt << 1, l, mid
#define rson rt << 1 | 1, mid + 1, r
#define lowbit(x) x &(-x)
#define pii pair<int, int>
#define fi first
#define se second
const int N = 1e6 + 5;
LL a[N];
LL ans[N];
bool vis[N];
LL Abs(LL x)
{
    return x < 0 ? -x : x;
}
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int n;
        scanf("%d", &n);
        a[0] = 0;
        _rep(1, n, i)
        {
            scanf("%lld", a + i);
            a[i] += a[i - 1];
        }
        LL a0 = 0, an = a[n], Max = 0;
        int A0, AN;
        sort(a, a + n + 1);
        memset(vis, 0, sizeof vis);
        if (a0 > an)
            swap(a0, an);
        _rep(0, n, i) if (a0 == a[i])
        {
            A0 = i;
            break;
        }
        _rep(0, n, i) if (an == a[i])
        {
            AN = i;
            break;
        }
        int l = 0, r = n;
        for (int i = A0; i >= 0; i -= 2)
            ans[l++] = a[i], vis[i] = 1;
        for (int i = AN; i <= n; i += 2)
            ans[r--] = a[i], vis[i] = 1;
        _rep(0, n, i) if (!vis[i]) ans[l++] = a[i];
        _rep(1, n, i) Max = max(Max, Abs(ans[i] - ans[i - 1]));
        printf("%lld\n", Max);
    }
}
```