6750. 房屋与学校 (Houses and Schools)
时间限制：1000 MS 内存限制：256 MB
题目描述
## 题目描述 一条街道上排布着 $n$ 栋房屋，编号依次为 $1, 2, \dots, n$。房屋 $a$ 和房屋 $b$ 之间的距离为 $|a-b|$。我们已知每栋房屋中的儿童数量。 你的任务是设立 $k$ 所学校，每所学校必须建在某一栋房屋内。随后，每名儿童都将前往距离其最近的学校上学。若采取最优设立策略，所有儿童的上学总步行距离最小是多少？ ## 输入格式 第一行包含两个整数 $n$ 和 $k$，分别表示房屋数量和学校数量。房屋编号为 $1, 2, \dots, n$。 第二行包含 $n$ 个整数 $c\_1, c\_2, \dots, c\_n$，依次表示每栋房屋中的儿童数量。 ## 输出格式 输出一个整数，表示最小总步行距离。 ## 输入输出样例 ### 输入 #1 ``` 6 2 2 7 1 4 6 4 ``` ### 输出 #1 ``` 11 ``` ### 样例解释 在房屋 $2$ 和房屋 $5$ 设立学校。 ## 说明/提示 ### 数据规模与约定 * $1 \le k \le n \le 3000$ * $1 \le c\_i \le 10^9$