A2209 | 奔跑奶牛
来源USACO / 2013
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
农夫约翰的牧场围栏上出现了一个洞，有 $N$（$1\le N\le 1000$）只牛从这个洞逃出了牧场。这些出逃的奶牛很狂躁，他们在外面到处搞破坏，每分钟每头牛都会给约翰带来 $1$ 美元的损失。约翰必须用缰绳套住所有的牛，以停止他们搞破坏。
幸运的是，奶牛们都在牧场外一条笔直的公路上，牧场的大门恰好位于公里的 $0$ 点处。约翰知道每头牛距离牧场大门的距离 $P_i$（$-5\times10^5\le P_i\le5\times 10^5$，$P_i\ne0$）。
约翰从农场大门出发，每分钟移动一个单位距离，每到一头牛所在的地点，约翰就会给它套上缰绳，套缰绳不花时间。按怎样的顺序去给牛套缰绳才能使约翰损失的费用最少？
幸运的是，奶牛们都在牧场外一条笔直的公路上，牧场的大门恰好位于公里的 $0$ 点处。约翰知道每头牛距离牧场大门的距离 $P_i$（$-5\times10^5\le P_i\le5\times 10^5$，$P_i\ne0$）。
约翰从农场大门出发，每分钟移动一个单位距离，每到一头牛所在的地点，约翰就会给它套上缰绳，套缰绳不花时间。按怎样的顺序去给牛套缰绳才能使约翰损失的费用最少？
输入格式
* 第 1 行：奶牛数量，N。
* 第 2..N+1 行：第 i+1 行包含整数P_i。
* 第 2..N+1 行：第 i+1 行包含整数P_i。
输出格式
* 第 1 行：损坏的最低总成本。
输入输出样例
输入 #1
4 -2 -12 3 7
输出 #1
50
四头奶牛被放置在位置：-2、-12、3 和 7。
最佳访问顺序为 -2、3、7、-12。FJ 在 2 分钟内到达位置 -2，对那头奶牛造成总共 2 美元的伤害。
然后他移动到位置 3（距离：5），该位置的累积伤害为 2 + 5 = 7 美元。
他又花了 4 分钟到达 7，那头牛的成本是 7 + 4 = 11 美元。
最后，他花了 19 分钟去 -12，成本为 11 + 19 = 30 美元。
总伤害为 2 + 7 + 11 + 30 = 50 美元。
最佳访问顺序为 -2、3、7、-12。FJ 在 2 分钟内到达位置 -2，对那头奶牛造成总共 2 美元的伤害。
然后他移动到位置 3（距离：5），该位置的累积伤害为 2 + 5 = 7 美元。
他又花了 4 分钟到达 7，那头牛的成本是 7 + 4 = 11 美元。
最后，他花了 19 分钟去 -12，成本为 11 + 19 = 30 美元。
总伤害为 2 + 7 + 11 + 30 = 50 美元。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？