luogu#P6246. [IOI2000] 邮局 加强版 加强版

    ID: 10263 远端评测题 2000~6000ms 250MiB 尝试: 8 已通过: 2 难度: 7 上传者: 标签>二分查找凸完全单调性凸单调IOI2000O2优化

[IOI2000] 邮局 加强版 加强版

题目背景

看到你时总是感觉清风徐徐,

本以为和你相识不会是偶遇,

奈何你犹如过客、化作秋雨,

只是经过我生命的一瓢柳絮,

从不会真正有童话似的结局.

我静静地写尽这些躁言丑句,

本以为可以稍稍地缓解抑郁.

却是徒增一场悲伤的脑补剧.

你问我为什么说这么多?

因为这题是加强版的 [IOI2000]邮局.

题目描述

高速公路旁边有 nn 个村庄。高速公路表示为整数轴,每个村庄的位置用单个整数坐标标识。两个位置之间的距离是其整数坐标差的绝对值。

现在要建立 mm 个邮局,邮局将建在一些,但不一定是所有的村庄中。为了建立邮局,应选择他们建造的位置,使每个村庄与其最近的邮局之间的距离总和最小。

你要编写一个程序,已知村庄的位置和邮局的数量,计算每个村庄和最近的邮局之间所有距离的最小可能的总和。

输入格式

第一行包含两个整数,分别表示村庄的数量 nn 和邮局的数量 mm

第二行共 nn 个整数,表示每个村庄的坐标,第 ii 个整数表示第 ii 个村庄的坐标 aia_i

输出格式

输出一行一个整数表示答案。

5 2
0 1 2 3 4
3

提示

数据规模与约定

本题共五个测试点,各测试点信息如下:

测试点编号 n=n = aia_i \leq
1 5000050000 6×1046 \times 10^4
2 150000150000 2×1052 \times 10^5
3 299998299998 5×1055 \times 10^5
4 499998499998 10610^6
5 499999499999 2×1062\times 10^6

对于全部的测试点,保证 1mn5×1051 \leq m \leq n \leq 5 \times 10^50ai2×1060 \leq a_i \leq 2\times 10^6,且 aia_i 的值在对应范围内均匀随机。

保证最终答案不超过 10910^9