#2131. The Cow Run

The Cow Run

题目描述

农夫约翰的牧场围栏上出现了一个洞,有N(1<=N<=1,000)\red{N(1 <= N <= 1,000)}只牛从这个洞逃出了牧场。这些出逃的奶牛很狂躁,他们在外面到处搞破坏,每分钟每头牛都会给约翰带来1\red{1}美元的损失。约翰必须用缰绳套住所有的牛,以停止他们搞破坏。

幸运的是,奶牛们都在牧场外一条笔直的公路上,牧场的大门恰好位于公里的0\red{0}点处。约翰知道每头牛距离牧场大门的距离Pi(500,000<=Pi<=500,000,Pi!=0)\red{P_i(-500,000 <= P_i <= 500,000, P_i != 0)}

约翰从农场大门出发,每分钟移动一个单位距离,每到一头牛所在的地点,约翰就会给它套上缰绳,套缰绳不花时间。按怎样的顺序去给牛套缰绳才能使约翰损失的费用最少?

输入格式

1\red{1 }行:奶牛数量,N\red{N}

2..N+1\red{2..N+1 }行:第 i+1\red{i+1 }行包含整数 Pi\red{P_i}

输出格式

1\red{1 }行:损害的最低总成本。

样例

输入样例

4 
-2 
-12 
3 
7

输出样例

50

提示

四头奶牛放置在以下位置:2\red{-2}12\red{-12}3\red{3 }7\red{7}

最佳访问顺序为2\red{-2}3\red{3}7\red{7}12\red{-12}FJ\red{FJ }2\red{2 }分钟内到达位置 2\red{-2,}总共对那头牛造成 2\red{2 }美元的伤害。

然后,他前往位置 3\red{3(}距离:5\red{5)},该位置对那头牛的累积伤害为 2+5=7\red{2 + 5 = 7 }美元。

他花了 4\red{4 }分钟才到达 7\red{7,}这头牛的成本是 7+4=11\red{7 + 4 = 11 }美元。

最后,他花了 19\red{19 }分钟到达 12\red{-12,}成本为 11+19=30\red{11 + 19 = 30 }美元。

总伤害为 2+7+11+30=50\red{2 + 7 + 11 + 30 = 50 }美元。