洛谷 P8684 [蓝桥杯 2019 省 B] 灵能传输

思路：前缀和+排序+贪心

这道题属于思维量很大的那种，并且很难想到，就连最简单的知识点前缀和在思考的时候都很难联系到。

我们可以看到样例里面，(ai−1​,ai​,ai+1​)←(ai−1​+ai​,−ai​,ai+1​+ai​)这个东西，我们假设前缀和的数组为s[i]，并且设s[0]=0，也就是从下标1开始存储。那么我们可以看到，原先的s[i-1],会变成了:

s[i-1]=s[i-1]+a[i].而s[i1]+a[i]则是s[i]。而s[i]=s[i]-a[i]，也就是s[i]=s[i-1]。换句话说，s[i]与s[i-1]的数值交换了！这样我们可以知道了，在进行灵能传递的时候，前缀和会发生交换。而我们需要求的稳定值，也就是max(abs(a[i]))，也就转化成了max(abs(s[i]-s[i-1]))。

其实，如果说0-n的范围之内都可以进行交换，这道题就直接排序一下，就出结果了，这道题就结束了。难的在下一个点上：也就是两边的端点是固定的，之后中间这些数会发生交换！

所以我们不得不考虑这种情况下我们该怎么办。我们其实可以从全部都可以排序的那个情况得出启示。假设两端点也可以动，那么，我们排序之后找到的最值，一定是建立在单调序列的基础上进行的。因为返回的最大值，肯定是这之间差值最大的那一个。

OK，照着这种观点，我们就需要用贪心的思路进行思考了，那就是尽量让我们这个固定两个端点的序列尽可能的单调。那么怎么做才能做到这一点呢？

我们可以在纸上画一下，发现如果两个端点固定，怎么画都不可能是单调的，而且，肯定会得到一个拥有两个拐点的曲线。因为两个端点的数值不明，并且中间的数值也不知道大小如何，我们就只能画出类似于这样的图像：

需要拥有一些数学知识，要想让曲线尽可能的单调，我们需要让两个拐点的曲线的重叠部分变得最少才行。其实说句人话，也就是让中间的线单调且长一点。

先说结论：在左端点<右端点，并且曲线的极小值在靠近左端点的位置，极大值靠近右端点的位置，这样才会保证两个拐点的曲线的重叠部分尽可能的少，也就是单调的部分多一点。就比如两个二次函数，一个开口向上，一个开口向下，我们在连接这两个函数时，可能会发生重叠，但是我们需要让重叠最少，这样函数中间的这一部分才会更长。这就是贪心的思路。

那么，实现方面，代码思路是这样的：首先我们需要求出来这个序列的前缀和。

然后，我们需要取出前缀和数组里面的两个端点，s[0]和s[n]，我们去比较他们的端点，看看哪一个小，哪一个大，肯定是小的在左边，大的在右边，所以如果s0>sn那么直接交换就行。

之后，我们再进行排序，从小到大。大家不要怕排序找不到这两个端点，我们排序的目的是为了能够方便找端点。排序之后，我们需要知道这两个端点现在在这个排序序列里面的位置。所以，需要开for循环去找。找到这两个端点的位置之后，下面是重头戏：

既然我们需要让单调序列最长，那么我们需要找到从左端点开始之后的最小值，和右端点开始之后的最大值。因为这个序列现在是从小到大排序的，所以，在找左端点之后的最小值时，我们直接在序列的左边一个一个遍历找。同理，右端点就向右边找。但是在循环写的时候需要+=2和-=2。为什么？

这就涉及到差值的问题了，我们需要知道的是，如果我们是一个一个的走，在到达最小值的时候，我们需要跨很大的一个步子，而2是能够保证差值最小的步子了。这里可以参照这篇题解：灵能传输-蓝桥杯_蓝桥杯灵能传输-CSDN博客

之后就是对于Max求稳定度就行了：

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<cmath> 
#include<vector>
#include<algorithm>
#include<stack>
#include<queue>
#include <iomanip>
#include<sstream>
#include<numeric>
#include<map>
#include<limits.h>
#include<set>
#define int long long
#define MAX 300050
#define _for(i,a,b) for(int i=a;i<(b);i++)
#define ALL(x) x.begin(),x.end()
using namespace std;
typedef pair<int, int> PII;
int n, m;
int counts=INT_MAX;
int a, b;
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
queue<PII>q;
int res = 0;
int arr[MAX];
int s[MAX];
int f[MAX];
int st[MAX];
void solve() {
    cin >> n;
    s[0] = 0;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        s[i] = s[i - 1] + arr[i];
    }
    int s0 = s[0];
    int sn = s[n];
    if (s0 > sn) {
        swap(s0, sn);
    }
    sort(s, s + n + 1);
    for (int i = 0; i <= n; i++) {
        if (s[i] == s0) {
            s0 = i;
            break;
        }
    }
    for (int i = 0; i <= n; i++) {
        if (s[i] == sn) {
            sn = i;
            break;
        }
    }
    int l = 0;
    int r = n;
    for (int i = s0; i >= 0; i -= 2) {
        f[l++] = s[i];
        st[i] = 1;
    }
    for (int i = sn; i <= n; i += 2) {
        f[r--] = s[i];
        st[i] = 1;
    }
    for (int i = 0; i <= n; i++) {
        if (!st[i])
            f[l++] = s[i];
    }
    for (int i = 1; i <= n; i++)
        res = max(res, abs(f[i]-f[i-1]));
    cout << res << endl;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> m;
    while (m--) {
        res = 0;
        memset(st, 0, sizeof(st));
        solve();
    }
    return 0;
}