← 返回题目

题库练习结算日

← 上一题下一题 →

A2036 | $结算日$

来源USACO

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

“不放债不借债”，贝西多么希望自己可以遵循这个忠告。她已经和她的 $N(1 \leq N \leq 100,000)$ 个朋友有了债务关系，或者借债了，或者放债了。她的 $N$ 个朋友依次标号为 $1\dots N$。 结算日终于来临了。她知道，朋友欠她的钱比她欠朋友的钱多。她的朋友们分布在一条直线上，第 $i$ 头奶牛站的位置距离谷仓 $i$ 米。贝西打算沿着这条直线行走，从欠她钱的奶牛手里收钱回来，并且还钱给她欠钱的奶牛。 当她沿直线移动的时候，她可以要求任何欠她钱的奶牛还全部的钱。当她有足够的钱可以还清她的某个债，就可以把钱给对应的奶牛还清她的债。奶牛 $i$ 欠贝西 $D_i$ 元 $(-1,000 \leq D_i \leq 1,000,D_i \neq 0)$，负数表示贝西欠奶牛 $i$ 钱。 贝西从谷仓出发，位置为 $0$，初始贝西没有钱。贝西收回她的所有借债，并且还清她的欠债所需行走的最短距离是多少？注意：她必须在最后一头奶牛所在的位置，完成她的行走。

输入格式

第一行，一个整数 $N$ 接下来第 $2 \dots N+1$ 行，第 $i+1$ 行包含一个整数 $D_i$

输出格式

一个整数，贝西收回借债并且还清欠债，所需要行走的最短距离（单位为米）

输入输出样例

输入 #1

输出 #1

C++ 编辑器

输入

输出