蓝桥杯-灵能传输-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

样例输入

样例输出

思路：

题目给定我们一个数组，要求我们通过多次操作后使得这个数组的最大值最小。这个操作题目中也有介绍，就是选中除去首尾数组的一个数，使得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[n]，如果不符合则交换他俩的值。

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

如图

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

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

1. T=int(input())
2. for p in range(T):
3.     n=int(input())
4.     a=list(map(int,input().split()))
5.     s=[0]+a
6. for i in range(1,n+1):
7.         s[i]+=s[i-1]
8.     sn=s[n]
9.     s.sort()
10.     a=[0 for i in range(n+1)]
11.     s0=0
12. if s0>sn:
13.         sn,s0=s0,sn
14. for i in range(n+1):
15. if s[i]==s0:
16.             s0=i
17.             break
18. for i in range(n,-1,-1):
19. if s[i]==sn:
20.             sn=i
21.             break
22.     l=0
23.     r=n
24.     a[n]=s[n]
25.     vis=[True for i in range(n+1)]
26. for i in range(s0,-1,-2):
27.         a[l]=s[i]
28.         vis[i]=False
29.         l+=1
30. for i in range(sn,n+1,2):
31.         a[r]=s[i]
32.         vis[i]=False
33.         r-=1
34. for i in range(n+1):
35. if vis[i]:
36.             a[l]=s[i]
37.             l+=1
38.     res=0
39. for i in range(n):
40.         res=max(res,abs(a[i+1]-a[i]))
41.     print(res)