Codeforces Round 611 (Div. 3) |
---|
Закончено |
На бесконечной числовой прямой находятся $$$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$$$ должны быть различными.
Если существует несколько ответов, выведите любой.
2 6 1 5
8 -1 2 6 4 0 3
3 5 0 3 1
7 5 -2 4 -1 2
Название |
---|