CF1283D Christmas Trees

在一条无限的数轴上有 $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 \times 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 \times 10^9 \le y_j \le 2 \times 10^9$），表示每个人的位置。所有 $y_j$ 必须互不相同，且 $x_1, x_2, \dots, x_n, y_1, y_2, \dots, y_m$ 也必须互不相同。 如果有多组答案，输出任意一组均可。

由 ChatGPT 4.1 翻译