← 返回题目列表

AtCoder · tkppc2016_f

F. NPC 之家

中文机器翻译题面 查看原题

問題文

检查完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