分数: 366 分
问题陈述
有 N 沿自西向东笔直道路延伸的城市。的 i第城市位于距离 X_i 从西端开始(城市不一定是从西到东编号)。
高桥正试图通过在这些城市之间安装双向通信线路来构建抗灾通信网络。任意两个城市之间可以直接安装一条通信线路,城市之间安装一条通信线路的成本 i 和城市 j is |X_i - X_j|。但是,以下条件适用:
- 同一对城市之间不能安装多条通信线路。
- 每条通信线路仅连接其端点的两个城市。即使另一个城市在地理位置上位于两个城市之间,它也不与该线路相连。
构建的网络必须满足以下容灾条件:
- 对于任何单个城市 v,即使城市 v 以及所有直连城市的通讯线路 v 已从网络中删除,所有剩余城市仍然可以相互通信。
这里,“可以互相通信”是指在剩余城市和剩余通信线路组成的网络中,任意两个城市之间可以通过通信线路直达或者通过其他城市中继到达。
找出构建满足此条件的网络所需的安装通信线路的最低总成本。
约束
- 3 \leq N \leq 10^6
- 0 \leq X_i \leq 10^9
- X_i \neq X_j (i \neq j)
- 所有输入均为整数
输入
N X_1 X_2 \cdots X_N
- 第一行包含一个整数 N 代表城市数量。
- 第二行包含整数 X_1, X_2, \ldots, X_N 以空格分隔,代表每个城市距西端的距离。
输出
以整数形式输出构建满足条件的网络所需的最小总安装成本。
示例输入 1
4 0 2 5 9
示例输出 1
18
示例输入 2
5 10 1 7 3 20
示例输出 2
38
示例输入 3
10 42 5 100 17 63 88 29 74 1 56
示例输出 3
198
示例输入 4
25 1000 250 4300 120 9800 7600 3150 640 8750 5200 60 7000 1500 2400 9999 3600 8100 4700 5900 9300 2050 6800 7350 1110 5550
示例输出 4
19878
示例输入 5
3 0 1000000000 500000000
示例输出 5
2000000000