蓝桥杯-灵能传输-python

蓝桥杯-灵能传输-python

感谢大佬的讲解：

第十届蓝桥杯题目讲解(Java B组 IJ，C++ B组 BGH，C++/Java A组 CEHIJ)_哔哩哔哩_bilibili

题目描述

你控制着 nn 名高阶圣堂武士，方便起见标为 1,2,··· ,n。每名高阶圣堂武士需要一定的灵能来战斗，每个人有一个灵能值 a_iai​ 表示其拥有的灵能的多少，a_iai​非负表示这名高阶圣堂武士比在最佳状态下多余了 ai​ 点灵能，ai​ 为负则表示这名高阶圣堂武士还需要 ai​ 点灵能才能到达最佳战斗状态）。

现在系统赋予了你的高阶圣堂武士一个能力，传递灵能，每次你可以选择一个 i ∈ [2,n−1]i∈[2,n−1]​，若 ai​​ ≥ 0 则其两旁的高阶圣堂武士，也就是 i−1、i + 1​ 这两名高阶圣堂武士会从 ii​这名高阶圣堂武士这里各抽取 ai​ 点灵能；若 ai​<0​ 则其两旁的高阶圣堂武士，也就是 i−1,i+1 这两名高阶圣堂武士会给 i 这名高阶圣堂武士 −a​​ 点灵能。形式化来讲就是 ai−1​+=ai​,ai+1​+=ai​,ai​−=2ai​​。

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

输入描述

本题包含多组询问。

输入的第一行包含一个正整数 TT 表示询问组数。 接下来依次输入每一组询问。

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

接下来一行包含 nn 个数 a_1,a_2,··· ,a_na1​,a2​,⋅⋅⋅,an​。

其中，T≤3，3≤n≤300000，∣ai∣≤10^9

样例输入

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

样例输出

3
0
3

 思路：

题目给定我们一个数组，要求我们通过多次 *** 作后使得这个数组的最大值最小。这个 *** 作题目中也有介绍，就是选中除去首尾数组的一个数，使得ai−1​+=ai​,ai+1​+=ai​,ai​−=2ai​​。

所有的加减 *** 作都是在数组内部进行的，对数组和不会有影响，所以我们可以用前缀和对这个 *** 作进行简化。

a[i−1]​​​ 更新为 a[i] + a[i-1]a[i]+a[i−1]​​，那么 s[i-1]s[i−1]​ 的新值等于原来的 s[i]s[i]；a[i]a[i] 更新为 -2a[i]−2a[i]，那么 s[i]s[i] 的新值等于原来的 s[i-1]s[i−1]；a[i+1]a[i+1] 更新为 a[i] + a[i+1]a[i]+a[i+1]， s[i+1]s[i+1] 的值保持不变。

经过一次 *** 作后，s[i]s[i]​​​​​ 和 s[i-1]互相交换，s[i+1]​​​​​ 不变。而 s[i-1]、s[i]​​​​​、s[i+1]​​​​​ 这 3​​​​​ 个数值还在，没有出现新的数值。设 a[0] = 0，观察前缀和数组 s[0]​​​​​、s[1]​​​​​、s[2]​​​​​、⋯​​​​​、s[n−1]​​​​​、s[n]​​​​​。除了s[0]​​​​，s[n]​​​ 外，其他的 s[1]​、s[2]、⋯、s[n-1]s[n−1]，经过多次 *** 作后，每个 s[i]s[i] 能到达任意位置。而我们所求的最小的最大值a[i]可以通过s[i]-s[i-1]求得。

为了让 *** 作后的s[]数组的max(s[i]-s[i-1])最小，就是使得相邻的s[i]相差最小。因为我们的a[0]和a[n]是不可以改变的，所以分为两种情况：

一：

s[0] 是最小的，s[n] 是最大的。 我们把 s[]s[] 排序后，max{|s[i]-s[i-1]}就是解了。

二：

当s[0]不是最小值，s[n]也不是最大值。

首先我们要保证s[0]

因为s[0]和s[n]是不变的，所以我们发现先从s[0]到min，再从min到max，最后从max到s[n]这样的走法使得相邻的s[i]最小。

如图

 将上图的点压倒y轴上可以得到这样的图

 之后我们发现隔一个点蹦的方法可以使得相邻的s[i]的差最小，是一组最优解。这样 *** 作后，得到了新的前缀和数组，此时的前缀和数组的差的最大值就是我们的答案

T=int(input())
for p in range(T):
    n=int(input())
    a=list(map(int,input().split()))
    s=[0]+a
    for i in range(1,n+1):
        s[i]+=s[i-1]
    sn=s[n]
    s.sort()
    a=[0 for i in range(n+1)]
    s0=0
    if s0>sn:
        sn,s0=s0,sn
    for i in range(n+1):
        if s[i]==s0:
            s0=i
            break
    for i in range(n,-1,-1):
        if s[i]==sn:
            sn=i
            break
    l=0
    r=n
    a[n]=s[n]
    vis=[True for i in range(n+1)]
    for i in range(s0,-1,-2):
        a[l]=s[i]
        vis[i]=False
        l+=1
    for i in range(sn,n+1,2):
        a[r]=s[i]
        vis[i]=False
        r-=1
    for i in range(n+1):
        if vis[i]:
            a[l]=s[i]
            l+=1
    res=0
    for i in range(n):
        res=max(res,abs(a[i+1]-a[i]))
    print(res)