#P6719. [2019山东省队集训第一轮]post
[2019山东省队集训第一轮]post
[2019山东省队集训第一轮]Post
题目描述
有一条长度为 的环形公路,路上有 个村庄,坐标分别为 。多个村庄可以位于同一坐标。
公路上坐标 之间的距离为沿环形公路行走的最短距离:
$$\operatorname{dist}(a,b)=\min\bigl(|a-b|,\ L-|a-b|\bigr).$$你要在公路的整数坐标处建立恰好 个邮局,坐标为 ,使每个村庄到最近邮局的距离之和最小,即最小化
$$\sum_{i=1}^{n}\min_{1\le j\le k}\operatorname{dist}(a_i,c_j).$$邮局坐标允许相同。输出最小距离和及任意一组达到最优值的邮局位置。
输入格式
第一行三个正整数 。
第二行 个整数 ,按非降顺序给出村庄坐标。
输出格式
第一行输出一个整数,表示最小距离和。
第二行输出 个整数 ,须满足
若有多解,输出任意一解即可。
样例输入
5 2 10
1 3 4 7 9
样例输出
5
3 7
样例解释
将邮局建在 和 ,五个村庄到最近邮局的距离依次为 ,总和为 。
数据范围
所有数据满足
$$1\le n\le2\times10^5,\qquad 1\le k\le n,\qquad 1\le L\le10^{12},$$以及 。
- 的数据满足 。
- 的数据满足 (包含上述 )。
- 另外 的数据满足 。
- 另外 的数据满足 。
- 其余数据没有额外限制。