問題文
检查完NPC的动向后,小伊西诺姐姐接到了布置NPC房屋的任务。
在左右无限延伸的直线上,N一个人类 NPC 站在那里。
在那条直线上M设置 NPC 房屋。
然后每个 NPC 将返回距离他们最近的房子。
在这个游戏中,为了达到真实感,NPC的房子必须放置在使每个NPC返回家的距离总和最小的位置。
为了高效地执行这项任务,Joisino Onee 决定编写一个程序来找出每个 NPC 回家的最小总距离。
入力
输入是按以下格式从标准输入给出的。
N M X_1 X_2 : X_N
- 1该行显示 NPC 的数量。N,要安装的房屋数量M。 表示(1 ≦ N ≦ 1000, 1 ≦ M ≦ 1000)
- 接下来的 N 行i行中,X_i,i表示第几号NPC的位置。(-10^9 ≦ X_i ≦ 10^9)
配点
针对此问题设置了部分分数。
- 数据集 1 是 如果您遇到N ≦ 300, M ≦ 300满足条件并回答正确可得10分。
- 在数据集2中没有额外的限制,回答正确可得110分。
出力
输出各NPC回到家之前的距离总和的最小值。
入力例1
5 2 -3 -1 0 2 5
出力例1
6
- 例如,-1, 2当在…的位置建房时,NPC1, 2, 3是 您也可以写-1回到自己所在位置的家,NPC4, 5是 您也可以写2的位置的家,所以每个 NPC 返回家里的总距离是2 + 0 + 1 + 0 + 3 = 6变为。
- ,并且没有比这更短的每个 NPC 返回家里总距离的配置,因而6是答案。
入力例2
10 3 -3 12 -92 -45 -15 27 14 94 -39 75
出力例2
131