P8684 [蓝桥杯 2019 省 B] 灵能传输 题解

题目传送门

欢迎大家指出错误并联系这个蒟蒻

更新日志

• 2023-06-20 21:46 文章完成

【解析】

本题涉及到了 $3$ 种算法：前缀和，排序以及贪心

（1）前缀和
本题实际上要求通过某种灵能传输可以使得该序列的最大值最小。而由前缀和可知，当某一个前缀和序列保持有序（或前缀和序列表示的函数单调）时，其 $\max(s[i]-s[i-1])$ 的最大值可以达到最小。
通过对几个样例的观察我们不难发现：
1.当 $a[i]>0$ 时，若 $a[i-1]=a[i-1]+a[i]$，则$s[i-1]$ 等于原来的 $s[i]$。
2.若 $a[i]=a[i]-2a[i]$，则原 $s[i-1]=s[i-1]+s[i]$。
3.现 $s[i]=$ 现 $s[i-1]-a[i]=$ 原 $s[i]-a[i]=$ 原 $s[i-1]$。
这意味着除了 $s[0]$ 和 $s[n]$ 以外，$1\sim n$ 的任何 $s[i]$ 都可以进行互相交换，从而得到一个有序序列。而 $a[i]=s[i]-s[i-1]$ 也就意味着可以通过交换 $s[i]$ 的方式得到灵能传输后的最终结果。

（2）排序

for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i], s[i] = s[i - 1] + a[i]);
}
sort(s + 1, s + 1 + n);

当然，如果 $s[0]$ 和 $s[n]$ 也可以正常交换，则只需要将整个前缀和序列进行排序，即可直接得到一个单调函数，那么本题的推导到这一步就可以结束了，可以通过直接计算 $\max(s[i]-s[i-1])$ 的值获得最大值和最小值。但问题就在于 $s[0]$ 和 $s[n]$，即最终得到的序列不一定是单调的，所以接下来就要通过一系列操作解决序列不单调的问题。

（3）贪心
通过上述的分析可以得知，想要求出本题的最优解就是使得所求序列尽可能保持单调。通过画图可知，在两个端点无法移动的条件下，在对于整个前缀和序列进行排序时，总能得到一个拥有两个拐点且中间部分保持单调的函数。此时就应该往贪心上思考，即当一条有两个拐点的曲线的重叠部分最小时单调部分最多，而一条曲线符合下列情况时符合要求。
①左端点小于右端点，即 $s[0]<s[n]$。在记录 $s_0$ 和 $s_n$ 的值时需要进行一次判定，如果得到的左端点比右端点大，那么就将这两个端点交换（尽量保证得到的函数是一个中部递增的单调函数，其目的是将得到的所有函数都变成中部递增函数，这样就可以少算至少一半的数据）。

if (s0 > sn) {
    swap(s0, sn);
}

②极小值在极大值左边（刚刚的情况中，要求得到的函数一定是中部递增的，因此不仅需要控制函数中部的递增，还要控制最大值和最小值以使得中部函数递增）。这就要求在后续选点时应遵循 $s[0]$ 向左取，$s[n]$ 向右取，因为这样才能取得两边的极值。
因为已经将两个端点确定并保证了两者的顺序，也对前缀和序列进行了升序处理，于是此时得到了一个存放着递增的前缀和序列的有序数组（左右端点的位置已经发生改变，情况①中已经记录了两者位置）。
接下来需要从左端点的位置向左依次取点，从右端点的位置向右依次取点（从左端点向左依次取点并取得前缀和序列的最小值，从右端点向右依次取点并取得前缀和序列的最大值）。此时通过画图可以求得函数为两个端点有拐点且中部有序递增的函数。

int l = 0, r = n - 1;
for (int i = s0; i >= n; i -= 2) {
    f[l++] = s[i];
    st[i] = true;
}
for (int i = sn; i <= n; i += 2) {
    f[r--] = s[i];
    st[i] = true;
}
for (int i = 0; i <= n; i++) {
    if (st[i] == false) {
        f[l++] = s[i];
    }
}

因为图像中有两个拐点而且会形成两个重叠部分，所以想要得到最优解，就要使得求得的函数图像中的递增部分尽可能地多，这样拐点处的图像就会尽可能地少，即可保证序列 $f$ 为重叠部分最小的前缀和序列。
在通过特定规则将所有点都遍历完毕后，此时已经得到最优解的图像（前缀和序列）。最后就是求出所有前缀和表示的灵能值中的最大者（一定为正），该灵能值便是最终答案。

int res = 0;
for (int i = 1; i <= n; i++) {
    res = max(res, abs(f[i] - f[i - 1]));
}

$res$ 即为所求结果

【代码】

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;
typedef long long ll;
ll a[N];
ll s[N];
ll f[N];
bool st[N];
int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n;
        scanf("%d", &n);
        s[0] = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%lld", &a[i]);
            s[i] = s[i - 1] + a[i];
        }
        ll s0 = s[0];
        ll sn = s[n];
        if (s0 > sn) {
            swap(s0, sn);
        }
        sort(s, s + 1 + n);
        for (int i = 0; i <= n; i++) {
            if (s0 == s[i]) {
                s0 = i;
                break;
            }
        }
        for (int i = 0; i <= n; i++) {
            if (sn == s[i]) {
                sn = i;
                break;
            }
        }
        memset(st, false, sizeof st);
        int l = 0, r = n;
        for (int i = s0; i >= 0; i -= 2) {
            f[l++] = s[i];
            st[i] = true;
        }
        for (int i = sn; i <= n; i += 2) {
            f[r--] = s[i];
            st[i] = true;
        }
        for (int i = 0; i <= n; i++) {
            if (st[i] == false) {
                f[l++] = s[i];
            }
        }
        ll res = 0;
        for (int i = 1; i <= n; i++) {
            res = max(res, abs(f[i] - f[i - 1]));
        }
        printf("%lld\n", res);
    }
    return 0;
}