luogu#P4998. 信号站

信号站

题目背景

扶贫行动来到了Q村,扶贫队准备在Q村修筑信号站,让Q村不再“远离尘世”,让人们获得丰富的外界信息。

题目描述

Q村非常非常Qiong,整个村只有一条路。在这条路上,有N户人家,因为条件有限,所以一个点上可能有多户人家。因为山区运输条件落后,所以扶贫队只能修筑k个信号站,并且他们希望各电站的不合理值之和最小。信号站的不合理值是指该信号站到每户人家的距离之和。

扶贫队善于修筑电站,但是他们不擅长选址~~(因为数学不好QwQ)~~,他们希望你>>编程高手,来帮助他们选择修筑信号站的最佳地点,使得k个信号站的不合理值最小。

距离求解方法:若某信号站的坐标为x,某户人家的坐标为y,那么该信号站与该人家的距离为|x-y|(即取绝对值)。

数据保证人家数大于信号站数。放置信号站的位置坐标必须为整数。一个位置上只能放一个信号站。

输入格式

共2行,

第一行,读入n n k k ,分别代表人家数和信号站数;

第二行,读入各户人家的坐标ai ai (保证为整数),用空格隔开。

输出格式

仅一行,输出最小的不合理值之和。

7 2
1 1 2 2 3 3 4
13

提示

样例解释

在2和3的位置上放置信号站(方案不唯一)。

数据范围

对于 70% 70\% 的数据,n,k103 n,k\leq 10^3
对于 100% 100\% 的数据,n1000000,0ai106 n \leq 1000000, 0 \leq a_i \leq 10 ^ 6