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$ 两两不同;
- 所有输入均为整数。