A7714 | Cookies and Greedy Takahashi
时间限制2s
内存限制1024MB
通过 / 提交0/0
题目描述
数轴上有 $N$ 块饼干。第 $i$ 块饼干的坐标为 $A_i$。
高桥初始时位于数轴上的坐标 $0$ 处，并重复执行以下操作，直到拾取全部 $N$ 块饼干：
* 操作：移动到距离其当前位置最近的那块饼干所在坐标处（若存在多块距离相等的饼干，则选择坐标最小的那块），并拾取该饼干。
求高桥在拾取全部饼干过程中所经过的总路程。
高桥初始时位于数轴上的坐标 $0$ 处，并重复执行以下操作，直到拾取全部 $N$ 块饼干：
* 操作：移动到距离其当前位置最近的那块饼干所在坐标处（若存在多块距离相等的饼干，则选择坐标最小的那块），并拾取该饼干。
求高桥在拾取全部饼干过程中所经过的总路程。
输入格式
输入从标准输入中按以下格式给出：
> $N$
> $A_1$ $\dots$ $A_N$
> $N$
> $A_1$ $\dots$ $A_N$
输出格式
输出答案。
输入输出样例
输入 #1
4 -1 -4 2 -11
输出 #1
23
输入 #2
10 1 2 3 4 5 -1 -2 -3 -4 -6
输出 #2
17
**样例 1 解释：**
高桥的操作如下：
* 他从坐标 $0$ 移动到坐标 $-1$，拾取饼干。移动距离为 $1$。
* 他从坐标 $-1$ 移动到坐标 $-4$，拾取饼干。移动距离为 $3$。
* 他从坐标 $-4$ 移动到坐标 $2$，拾取饼干。移动距离为 $6$。
* 他从坐标 $2$ 移动到坐标 $-11$，拾取饼干。移动距离为 $13$。
因此，总移动距离为 $1+3+6+13=23$。
在第二次操作中，到坐标 $-4$ 处的饼干与到坐标 $2$ 处的饼干的距离均为 $3$，此时高桥选择移动到更小的坐标 $-4$。
### 限制条件
* $1 \leq N \leq 3\times 10^5$
* $-10^9 \leq A_i \leq 10^9$
* $A_i\neq 0$
* 所有 $A_i$ 互不相同。
* 所有输入值均为整数。
高桥的操作如下：
* 他从坐标 $0$ 移动到坐标 $-1$，拾取饼干。移动距离为 $1$。
* 他从坐标 $-1$ 移动到坐标 $-4$，拾取饼干。移动距离为 $3$。
* 他从坐标 $-4$ 移动到坐标 $2$，拾取饼干。移动距离为 $6$。
* 他从坐标 $2$ 移动到坐标 $-11$，拾取饼干。移动距离为 $13$。
因此，总移动距离为 $1+3+6+13=23$。
在第二次操作中，到坐标 $-4$ 处的饼干与到坐标 $2$ 处的饼干的距离均为 $3$，此时高桥选择移动到更小的坐标 $-4$。
### 限制条件
* $1 \leq N \leq 3\times 10^5$
* $-10^9 \leq A_i \leq 10^9$
* $A_i\neq 0$
* 所有 $A_i$ 互不相同。
* 所有输入值均为整数。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？