AT_abc471_c [ABC471C] Cookies and Greedy Takahashi

题目描述

数轴上有 $N$ 个位置掉落着饼干。第 $i$ 个饼干的位置坐标为 $A_i$。 高桥君初始位于数轴上的坐标 $0$,他重复执行以下操作,直到捡起所有 $N$ 个饼干: - **操作**:移动到离自己最近的未捡饼干所在坐标(如果有多个距离相同,则选择坐标最小的那个),然后捡起该饼干。 求高桥君捡起所有饼干所经过的总移动距离。

输入格式

输入第一行包含一个整数 $N$。 第二行包含 $N$ 个整数 $A_1, A_2, \dots, A_N$。

输出格式

输出一行一个整数,表示答案。

说明/提示

**【样例 1 解释】** 高桥君的行动如下: 1. 从坐标 $0$ 移动到坐标 $-1$,捡起饼干,移动距离为 $1$; 2. 从坐标 $-1$ 移动到坐标 $-4$,捡起饼干,移动距离为 $3$; 3. 从坐标 $-4$ 移动到坐标 $2$,捡起饼干,移动距离为 $6$; 4. 从坐标 $2$ 移动到坐标 $-11$,捡起饼干,移动距离为 $13$。 因此总移动距离为 $1 + 3 + 6 + 13 = 23$。 注意:在第 2 次行动中,坐标为 $-4$ 和 $2$ 的饼干距离当前位置 $-1$ 都为 $3$,但根据规则,高桥君选择坐标更小的 $-4$。 **【数据范围】** - $1 \le N \le 3 \times 10^5$; - $-10^9 \le A_i \le 10^9$; - $A_i \ne 0$; - $A_i$ 两两不同; - 所有输入均为整数。