分数: 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