luogu#P6246. [IOI2000] 邮局 加强版 加强版
[IOI2000] 邮局 加强版 加强版
题目背景
看到你时总是感觉清风徐徐,
本以为和你相识不会是偶遇,
奈何你犹如过客、化作秋雨,
只是经过我生命的一瓢柳絮,
从不会真正有童话似的结局.
我静静地写尽这些躁言丑句,
本以为可以稍稍地缓解抑郁.
却是徒增一场悲伤的脑补剧.
你问我为什么说这么多?
因为这题是加强版的 [IOI2000]邮局.
题目描述
高速公路旁边有 个村庄。高速公路表示为整数轴,每个村庄的位置用单个整数坐标标识。两个位置之间的距离是其整数坐标差的绝对值。
现在要建立 个邮局,邮局将建在一些,但不一定是所有的村庄中。为了建立邮局,应选择他们建造的位置,使每个村庄与其最近的邮局之间的距离总和最小。
你要编写一个程序,已知村庄的位置和邮局的数量,计算每个村庄和最近的邮局之间所有距离的最小可能的总和。
输入格式
第一行包含两个整数,分别表示村庄的数量 和邮局的数量 。
第二行共 个整数,表示每个村庄的坐标,第 个整数表示第 个村庄的坐标 。
输出格式
输出一行一个整数表示答案。
5 2
0 1 2 3 4
3
提示
数据规模与约定
本题共五个测试点,各测试点信息如下:
测试点编号 | ||
---|---|---|
1 | ||
2 | ||
3 | ||
4 | ||
5 |
对于全部的测试点,保证 ,,且 的值在对应范围内均匀随机。
保证最终答案不超过 。