#2744. The Cow Run

The Cow Run

题目描述

农夫约翰忘记在他的农场的围栏上修一个洞,他的 N\red{N }头奶牛 (1<=N<=1,000)\red{(1 <= N <= 1,000) }已经逃跑并横冲直撞!一头母牛在围栏外的每一分钟,都会造成价值一美元的 损失。

FJ\red{FJ }必须拜访每头奶牛,安装一个能安抚奶牛并阻止伤害的笼头。幸运的是,奶牛分布在农场外道路上的一条直线上的不同位置。FJ\red{FJ }知道每头奶牛 i(500,000<=Pi<=500,000,Pi!=0)\red{i (-500,000 <= P_i <= 500,000, P_i != 0) }相对于 FJ\red{FJ }开始的门(位置 0\red{0})的位置 Pi\red{P_i}

FJ\red{FJ}每分钟移动一个单位的距离,可以立即安装露背。请确定 FJ\red{FJ }应该访问奶牛的顺序,以便他可以最大限度地减少损害的总成本;在这种情况下,您应该计算最 小总伤害成本。

输入格式

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,3,7\red{-2,3,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}美元