↓Skip to main content
  1. Posts/

AtCoder-ARC189B Minimize Sum

·1 min·
Table of Contents

AtCoder-ARC189D Takahashi is Slime #

Solution 1 #

对 $x_i < x_{i+1} < x_{i+2} < x_{i+3}$ 进行操作, 结果变为 $x_i < x_{i} + x_{i+3} - x_{i + 2} < x_{i} + x_{i+3} - x_{i + 1} < x_{i+3}$ (这里重新排过序了). 观察差分从 $$x_{i + 1}- x_i, x_{i+2}-x_{i+1}, x_{i+3} - x_{i+2}$$ 变成 $$x_{i+3} - x_{i+2}, x_{i+2} - x_{i+1}, x_{i + 1} - x_{i}$$ 相当于交换了 $d_i$ 和 $d_{i+2}$ , 奇数下标的差分和偶数下标的差分可以在各自内部交换. 由于目标是和最小, 因此小的差分尽可能靠前.

代码如下:

if __name__ == '__main__':
    n = int(input())
    a = sorted(list(map(int, input().split())))
    d0, d1 = [], []
    for i in range(1, n):
        if i & 1:
            d1.append(a[i] - a[i - 1])
        else:
            d0.append(a[i] - a[i - 1])
    d0.sort()
    d1.sort()
    ans = x = a[0]
    for i in range(1, n):
        if i & 1:
            x += d1[i // 2]
        else:
            x += d0[i // 2 - 1]
        ans += x
    print(ans)