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

· · 题解

题面传送门

分析

先对灵能传递进行转化。

可以发现，如果把 a 做一遍前缀和得到数组 s，那么对于一次对 i 的灵能传递相当于把 s_i,s_{i-1} 交换。

我们令 s_0 = 0，剩下的就是把 s_{1 \sim n-1} 重新排列，使得 \max_{i=1}^{n}{\{|s_i-s_{i-1}|\}} 最小。

如果可以移动 s_0,s_n，那么直接将 s 排序，这样相邻的差是最小的。

通过上面的思路，不难想到这样的做法：

设 L = \min(s_0,s_n),R = \max(s_0,s_n)。先从 L 取到 s 最小值，再取到最大值，最后取到 R。

我们对 s_{1 \sim n-1} 排序后，取第一个大于等于 L 的位置 M，对于 1 \sim M-1 的数，分别放在 L,M 下面，从大到小地把数放在较小的一边，对 M+1 \sim n-1 的同理。

这样一定是相邻差最小的。

以放 1 \sim M-1 为例。如下图，考虑交换两个数 x,y，对于 x,y 上面的 p,q，根据前面的贪心策略，一定有 y \le x \le q \le p，因此交换后最大距离变大；对于 x,y 下面的 s,t 同理。

时间复杂度为 O(Tn \log n)。

代码

#include <bits/stdc++.h>
#define N 300005
#define ll long long
using namespace std;
int T,n;ll a[N],ans;
int main() {
    scanf("%d",&T);
    while(T--) {
        scanf("%d",&n);
        for(int i=1;i<=n;++i) scanf("%lld",&a[i]),a[i]+=a[i-1];
        sort(a+1,a+n);ans=0;
        ll L=0,R=a[n];if(L>R) swap(L,R);
        int m=lower_bound(a+1,a+n,L)-a;
        ll l=L,r=a[m];
        for(int i=m;i;--i) {
            if(l<r) swap(l,r);
            ans=max(ans,l-a[i]);
            l=a[i];
        }
        ans=max(ans,max(l-r,r-l));
        l=a[m],r=R;
        for(int i=m+1;i<n;++i) {
            if(l>r) swap(l,r);
            ans=max(ans,a[i]-l);
            l=a[i];
        }
        ans=max(ans,max(l-r,r-l));
        if(m==n) ans=max(ans,R-a[n-1]);
        printf("%lld\n",ans);
    }
    return 0;
}