盛日辉的博客
0%

蓝桥-灵能传输

发表于 更新于 分类于 ，

题目

https://www.lanqiao.cn/problems/196/learning/

思路

  1. 所有操作都是在数组内进行的，整个数组的和不变；
  2. 每次操作的三个数的和不变，因此考虑到用前缀和。
  3. 一次更新后，s[i-1]变为原来的s[i],s[i]变为原来的s[i-1],s[i+1]不变；
  4. 因此“一次加减操作”转变为“前两个前缀和的交换”。
  5. 两端的武士不向外传递灵能，但他们的灵能值也会改变，而s[n]是所有的和，不变。因此，s[0]=0，s[1]到s[n-1]可以交换到任意位置。
  6. 要求的东西就变成了求max{|s[i]-s[i-1|}尽量小。
  7. 先考虑简单情况，s[]都是正的，将他排序，相邻差最大的就是结果，因为如果不排序，相邻相减会大；
  8. https://blog.csdn.net/xuxiaobo1234/article/details/108095193
  9. 最后一步，我只能理解成：小于s[0]大于min部分的值要排列起来，使得相邻两数的差最大值最小化，从图像上想象就是，s[0]固定住，s[1]到s[p]（假设是这样的下标）升序排序，但都小于s[0]，然后隔一个的将数拆开成两部分，一部分降序地排列在s[0]后面，然后另一部分更在后面，这样能“使得相邻两数的差最大值最小化”。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
# 灵能传输

T = int(input())
for _ in range(T):
    n = int(input())
    arr = list(map(int, input().split()))
    # 计算前缀和
    s = [0] * (n + 1)
    for i, x in enumerate(arr):
        s[i + 1] = s[i] + x
    s0, sn = s[0], s[-1]
    if s0 > sn:
        s0, sn = sn, s0
    # print(s)
    s.sort()
    s0_idx = s.index(s0)
    sn_idx = s.index(sn)
    # print(s)
    # print(s0_idx)
    # print(sn_idx)
    res_sum = s.copy()
    L, R = 0, n
    vis = [True] * (n + 1)
    for i in range(s0_idx, -1, -2):
        res_sum[L] = s[i]
        L += 1
        vis[i] = False
    for i in range(sn_idx, n + 1, 2):
        res_sum[R] = s[i]
        R -= 1
        vis[i] = False
    for i in range(n + 1):
        if vis[i]:
            res_sum[L] = s[i]
            L += 1

    res = 0
    for i in range(1, len(res_sum)):
        res = max(res, abs(res_sum[i] - res_sum[i - 1]))

    print(res)