信号站
题目背景
扶贫行动来到了Q村,扶贫队准备在Q村修筑信号站,让Q村不再“远离尘世”,让人们获得丰富的外界信息。
题目描述
Q村非常非常Qiong,整个村只有一条路。在这条路上,有N户人家,因为条件有限,所以一个点上可能有多户人家。因为山区运输条件落后,所以扶贫队只能修筑k个信号站,并且他们希望各电站的不合理值之和最小。信号站的不合理值是指该信号站到每户人家的距离之和。
扶贫队善于修筑电站,但是他们不擅长选址~~(因为数学不好QwQ)~~,他们希望你>>编程高手,来帮助他们选择修筑信号站的最佳地点,使得k个信号站的不合理值最小。
距离求解方法:若某信号站的坐标为x,某户人家的坐标为y,那么该信号站与该人家的距离为|x-y|(即取绝对值)。
数据保证人家数大于信号站数。放置信号站的位置坐标必须为整数。一个位置上只能放一个信号站。
输入输出格式
输入格式
#### 共2行,
第一行,读入$ n $,$ k $,分别代表人家数和信号站数;
第二行,读入各户人家的坐标$ ai $(保证为整数),用空格隔开。
输出格式
仅一行,输出**最小**的不合理值之和。
输入输出样例
输入样例 #1
7 2
1 1 2 2 3 3 4
输出样例 #1
13
说明
#### 样例解释
在2和3的位置上放置信号站(方案不唯一)。
#### 数据范围
对于 $ 70\% $ 的数据,$ n,k\leq 10^3 $;
对于 $ 100\% $ 的数据,$ n \leq 1000000, 0 \leq a_i \leq 10 ^ 6 $。