← 返回题目列表

AtCoder · arc189_b

B. 最小化总和

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

有 N 棋子放置在数轴上。最初,所有碎片都放置在不同的坐标上。
棋子的初始坐标是 X_1, X_2, \ldots, X_N.
Takahashi 可以重复以下操作任意次数,可能为零。

选择一个整数 i 这样 1 \leq i \leq N-3,让 M 是两个位置之间的中点 i-th 和 (i+3)- 按坐标升序排列的第 块。
然后,移动每个 (i+1)-th 和 (i+2)- 按照坐标升序排列到对称位置的第 M.
在这个问题的约束下,可以证明,无论如何重复执行操作,所有棋子始终占据不同的坐标。

他的目标是最小化坐标的总和 N 件。
求最小可能的坐标总和 重复操作后 N 件。

约束

  • 4 \leq N \leq 2 \times 10^5
  • 0 \leq X_1 < X_2 < \cdots < X_N \leq 10^{12}
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
X_1 X_2 \ldots X_N

输出

打印最小可能的坐标总和 N 件。


示例输入 1

4
1 5 7 10

示例输出 1

21

如果高桥选择 i = 1,操作如下:

  • 按坐标升序排列的第 1 块和第 4 块的坐标为 1 和 10,所以坐标 M 在此操作中是 (1 + 10)/2 = 5.5.
  • 左起第二块从坐标移动 5 to 5.5 + (5.5 - 5) = 6.
  • 左起第三块从坐标移动 7 to 5.5 - (7 - 5.5) = 4.

经过此操作,四块的坐标之和为 1 + 4 + 6 + 10 = 21,这是最小的。因此,打印 21.


示例输入 2

6
0 1 6 10 14 16

示例输出 2

41