← 返回题目列表

AtCoder · awc0004_c

C. 温度调节成本最低

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

分数: 300 分

问题陈述

高桥要进行化学实验。

在这个实验中,他需要处理所有 N 试剂,每个恰好一次。试剂处理温度 i (1 \leq i \leq N) is H_i 度。

实验装置的温度初始设置为 0 度。为了处理试剂,必须将设备温度设置为与该试剂的处理温度完全匹配。高桥可以自由选择处理试剂的顺序。处理完所有试剂后,他必须将仪器温度恢复到 0 度完成实验。

将设备温度从 a 度至 b 度,能耗为 |a - b|.

如果处理试剂的顺序是 (p_1, p_2, \ldots, p_N) (排列 (1, 2, \ldots, N)),总能耗为

$$|H_{p_1}| + |H_{p_2} - H_{p_1}| + \cdots + |H_{p_N} - H_{p_{N-1}}| + |H_{p_N}|$$

这里,第一项对应于从初始状态改变的成本 0 度为第一个试剂的处理温度,最后一项对应于从最后一个试剂的处理温度返回到 0 度。

Takahashi 希望通过优化选择试剂处理顺序来最大限度地减少总能耗。求最小总能耗。

约束

  • 1 \leq N \leq 2 \times 10^5
  • -10^9 \leq H_i \leq 10^9
  • 所有输入均为整数

输入

N
H_1 H_2 \cdots H_N
  • 第一行包含一个整数 N,代表试剂数量。
  • 第二行包含 N 整数 H_1, H_2, \ldots, H_N 以空格分隔,代表每种试剂的处理温度。

输出

在单行上以整数形式输出最小总能耗。


示例输入 1

3
5 -3 2

示例输出 1

16

示例输入 2

5
10 -5 3 -8 7

示例输出 2

36

示例输入 3

8
100 -200 50 -150 300 -50 200 -100

示例输出 3

1000