Houses and Schools

题目描述

街道上有 $n$ 户房子，编号为 1,2,$\dots$,n。房子 a 和 b 之间的距离是 $|a-b|$。你知道每户有多少孩子。 你的任务是在若干房子里建立 $k$ 所学校，然后每个孩子去最近的一所学校。若你采取最优方案，孩子们步行的总距离最小值是多少？

输入格式

第一行包含两个整数 $n$ 和 $k$：房子的数量和学校的数量。房子编号为 1,2$\dots$,n。 接下来有 $n$ 个整数 $c_1,c_2,$$\dots$,$c_n$：每户的孩子数量。

输出格式

输出最小的总距离。

6 2
2 7 1 4 6 4

11

提示

$1 \le k \le n \le 3000$ $1 \le c_i \le 10^9$ 样例解释：在房子 2 和 5 处各建一所学校。

标签: CSES2087|先进技术

来源

CSES2087|先进技术