← 返回题目列表

Codeforces · 1283/D

D. 圣诞树

中文机器翻译题面 查看原题

无限数轴上有 $$$n$$$ 圣诞树。第 $$$i$$$ 树生长在位置 $$$x_i$$$ 处。所有 $$$x_i$$$ 保证是不同的。

每个整数点可以被圣诞树、人类占据或根本不被占据。非整数点不能被任何东西占据。

有 $$$m$$$ 人想要庆祝圣诞节。设 $$$y_1, y_2, \dots, y_m$$$ 为人员的位置(请注意,所有值 $$$x_1, x_2, \dots, x_n, y_1, y_2, \dots, y_m$$$ 都应该是不同的,所有 $$$y_j$$$ 都应该是整数)。您想要找到这样的人员排列,使得 $$$\sum\limits_{j=1}^{m}\min\limits_{i=1}^{n}|x_i - y_j|$$$ 的值尽可能最小(换句话说,所有人到最近的圣诞树的距离总和应该最小化)。

换句话说,令 $$$d_j$$$ 为第 $$$j$$$ 个人到最近的圣诞树的距离 ($$$d_j = \min\limits_{i=1}^{n} |y_j - x_i|$$$)。然后你需要选择这样的位置 $$$y_1, y_2, \dots, y_m$$$ 使得 $$$\sum\limits_{j=1}^{m} d_j$$$ 是可能的最小值。

输入

输入的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) — 圣诞树的数量和人数。

输入的第二行包含 $$$n$$$ 整数 $$$x_1, x_2, \dots, x_n$$$ ($$$-10^9 \le x_i \le 10^9$$$),其中 $$$x_i$$$ 是第 $$$i$$$ 圣诞树的位置。保证所有 $$$x_i$$$ 都是不同的。

输出

在第一行中打印一个整数 $$$res$$$ — $$$\sum\limits_{j=1}^{m}\min\limits_{i=1}^{n}|x_i - y_j|$$$ 的最小可能值(换句话说,就是所有人到最近的圣诞树的距离总和)。

在第二行中打印 $$$m$$$ 整数 $$$y_1, y_2, \dots, y_m$$$ ($$$-2 \cdot 10^9 \le y_j \le 2 \cdot 10^9$$$),其中 $$$y_j$$$ 是第 $$$j$$$ 个人的位置。所有 $$$y_j$$$ 应该是不同的,并且所有值 $$$x_1, x_2, \dots, x_n, y_1, y_2, \dots, y_m$$$ 应该是不同的。

如果有多个答案,请打印其中任何一个。

示例

输入 #1

2 6
1 5

输出 #1

8
-1 2 6 4 0 3

输入 #2

3 5
0 3 1

输出 #2

7
5 -2 4 -1 2