CSES2087 房屋与学校
#CS2087. 房屋与学校
房屋与学校
题目背景
翻译自 CSES-2087 题。
题目描述
在一条街道上，有 n 所房屋，编号为 1,2,...,n1, 2, ..., n1,2,...,n。房屋 a 和房屋 b 之间的距离是 ∣a−b∣|a - b|∣a−b∣。你知道每所房屋里有多少个孩子。
你的任务是建立 k 所学校，使得每所学校都位于某一所房屋中。然后，每个孩子都将前往最近的学校。请问，若你采取最优策略，孩子们的总步行距离最小是多少？
输入格式
第一行输入两个整数 n 和 k，分别表示房屋的数量和学校的数量。房屋的编号为 1,2,...,n1, 2, ..., n1,2,...,n。
接下来，输入 n 个整数 c1,c2,...,cnc_1, c_2, ..., c_nc1,c2,...,cn，表示每所房屋中的孩子数量。
输出格式
输出一个整数，表示孩子们的最小总步行距离。
样例
6 2
2 7 1 4 6 4
11
样例1解释 最优解是将学校设置在第 2 所房屋和第 5 所房屋。此时，孩子们的总步行距离为 1。
说明/提示
1≤ci≤1091 \leq c_i \leq 10^91≤ci≤109。