#P6719. [2019山东省队集训第一轮]post

    ID: 6569 传统题 2000ms 888MiB 尝试: 4 已通过: 2 难度: 10 上传者: 标签>动态规划字符串数据结构树状数组CF3000WQS二分分治单调队列优化

[2019山东省队集训第一轮]post

[2019山东省队集训第一轮]Post

题目描述

有一条长度为 LL 的环形公路,路上有 nn 个村庄,坐标分别为 a1,a2,…,ana_1,a_2,\ldots,a_n。多个村庄可以位于同一坐标。

公路上坐标 a,ba,b 之间的距离为沿环形公路行走的最短距离:

$$\operatorname{dist}(a,b)=\min\bigl(|a-b|,\ L-|a-b|\bigr).$$

你要在公路的整数坐标处建立恰好 kk 个邮局,坐标为 c1,c2,…,ckc_1,c_2,\ldots,c_k,使每个村庄到最近邮局的距离之和最小,即最小化

$$\sum_{i=1}^{n}\min_{1\le j\le k}\operatorname{dist}(a_i,c_j).$$

邮局坐标允许相同。输出最小距离和及任意一组达到最优值的邮局位置。

输入格式

第一行三个正整数 n,k,Ln,k,L。

第二行 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n,按非降顺序给出村庄坐标。

输出格式

第一行输出一个整数,表示最小距离和。

第二行输出 kk 个整数 c1,c2,…,ckc_1,c_2,\ldots,c_k,须满足

0≤c1≤c2≤⋯≤ck<L.0\le c_1\le c_2\le\cdots\le c_k<L.

若有多解,输出任意一解即可。

样例输入

5 2 10
1 3 4 7 9

样例输出

5
3 7

样例解释

将邮局建在 33 和 77,五个村庄到最近邮局的距离依次为 2,0,1,0,22,0,1,0,2,总和为 55。

数据范围

所有数据满足

$$1\le n\le2\times10^5,\qquad 1\le k\le n,\qquad 1\le L\le10^{12},$$

以及 0≤a1≤a2≤⋯≤an<L0\le a_1\le a_2\le\cdots\le a_n<L。

  • 10%10\% 的数据满足 n≤100n\le100。
  • 40%40\% 的数据满足 n≤2000n\le2000(包含上述 10%10\%)。
  • 另外 10%10\% 的数据满足 k≥10000k\ge10000。
  • 另外 20%20\% 的数据满足 k≤20k\le20。
  • 其余数据没有额外限制。