Codeforces Round 884 (Div. 1 + Div. 2) |
---|
Закончено |
Единственное отличие между этой задачей и сложной версией — в ограничениях на $$$t$$$ и $$$n$$$.
Вам дан массив из $$$n$$$ положительных целых чисел $$$a_1,\dots,a_n$$$, а также целое (возможно, отрицательное) число $$$c$$$.
Среди всех возможных перестановок $$$b_1,\dots,b_n$$$ массива $$$a_1,\dots,a_n$$$, рассмотрим минимально возможное значение $$$$$$\sum_{i=1}^{n-1} |b_{i+1}-b_i-c|.$$$$$$ Найдите лексикографически наименьшую перестановку $$$b$$$ массива $$$a$$$, на которой достигается этот минимум.
Последовательность $$$x$$$ лексикографически меньше последовательности $$$y$$$, если и только если выполняется один из следующих пунктов:
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^3$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит два целых числа: $$$n$$$ и $$$c$$$ ($$$1 \le n \le 5 \cdot 10^3$$$, $$$-10^9 \le c \le 10^9$$$).
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1,\dots,a_n$$$ ($$$1 \le a_i \le 10^9$$$).
Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$5 \cdot 10^3$$$.
Для каждого набора входных данных выведите $$$n$$$ целых чисел $$$b_1,\dots,b_n$$$, задающих лексикографически наименьшую перестановку $$$a$$$, на которой достигается минимум $$$\sum\limits_{i=1}^{n-1} |b_{i+1}-b_i-c|$$$.
36 -73 1 4 1 5 93 21 3 51 27182818
9 3 1 4 5 1 1 3 5 2818
В первом наборе входных данных можно доказать, что минимальное значение $$$\sum\limits_{i=1}^{n-1} |b_{i+1}-b_i-c|$$$ равно $$$27$$$, а перестановка $$$b = [9,3,1,4,5,1]$$$ является лексикографически наименьшей перестановкой $$$a$$$, на которой достигается этот минимум: $$$|3-9-(-7)|+|1-3-(-7)|+|4-1-(-7)|+|5-4-(-7)|+|1-5-(-7)| = 1+5+10+8+3 = 27$$$.
Во втором наборе входных данных минимально возможное значение $$$\sum\limits_{i=1}^{n-1} |b_{i+1}-b_i-c|$$$ равно $$$0$$$, при этом $$$b = [1,3,5]$$$ является лексикографически наименьшей перестановкой $$$a$$$, на которой достигается этот минимум.
В третьем наборе входных данных существует всего одна перестановка $$$b$$$.
Название |
---|