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