Problem5916--排队问题

5916: 排队问题

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

Description

$n$ 个身高不同的小朋友,分别站在编号为 $1 \sim n$ 的格子里。我们希望小朋友们能够按照身高的顺序从低到高站在这 $n$ 个格子里。
按照 $1 \sim n$ 的顺序给出站在对应序号方格内小朋友的身高,问所有小朋友总共需要移动多少个格子,才能按照身高从低到高的顺序排好队?
注:①从格子 $3$ 移动到格子 $1$,需要移动 $2$ 个格子。 ②同一个格子只能站一个小朋友。

Input

第一行:一个数 $n\ (1 \leq n \leq 10,000)$。
后面 $n$ 行:每行 $1$ 个数,表示小朋友的身高。身高不会超过 $1,000,000mm$。

Output

输出所有小朋友移动距离之和。

Sample 1 Input

4
1220
1210
1200
1250

Sample 1 Output

4
$4$ 个小朋友,身高分别是:$1220\ 1210\ 1200\ 1250$。
按照身高顺序排好后,应该是:$1200\ 1210\ 1220\ 1250$。
身高 $1200$ 的小朋友需要向后移动 $2$ 格;身高 $1220$ 的小朋友需要前移动 $2$ 格;身高 $1210$ 和 $1250$ 的小朋友不需要移动;$4$ 个小朋友总共需要移动 $2 + 2 = 4$ 格。

Sample 2 Input

4
1220
1200
1210
1250

Sample 2 Output

4
$4$ 个小朋友,身高分别是:$1220\ 1200\ 1210\ 1250$。
按照身高顺序排好后,应该是:$1200\ 1210\ 1220\ 1250$。
身高 $1200$ 的小朋友需要向前移动 $1$ 格,身高 $1210$ 的小朋友需要向前移动 $1$ 格,身高 $1220$ 的小朋友需要向后移动 $2$ 格,身高 $1250$ 的小朋友不需要移动,$4$ 个小朋友总共需要移动 $1 + 1 + 2 = 4$ 格。

HINT

题目来源:51Nod 2353

Source/Category