← 返回题目列表

Codeforces · 1844/F1

F1. 最小成本排列(简单版)

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

这个问题和困难版本之间的唯一区别是对 $$$t$$$ 和 $$$n$$$ 的约束。

给定一个由 $$$n$$$ 正整数 $$$a_1,\dots,a_n$$$ 和一个(可能是负数)整数 $$$c$$$ 组成的数组。

在数组 $$$a_1,\dots,a_n$$$ 的所有排列 $$$b_1,\dots,b_n$$$ 中,考虑 $$$$$$\sum_{i=1}^{n-1} |b_{i+1}-b_i-c|.$$$$$$ 查找字典顺序上最小的排列达到此最小值的数组 $$$a$$$ 的 $$$b$$$。

当且仅当满足以下条件之一时,序列 $$$x$$$ 按字典顺序小于序列 $$$y$$$:

- $$$x$$$ 是 $$$y$$$ 的前缀,但是 $$$x \ne y$$$;
- 在 $$$x$$$ 和 $$$y$$$ 不同的第一个位置,序列 $$$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|$$$。

示例

输入 #1

3
6 -7
3 1 4 1 5 9
3 2
1 3 5
1 2718
2818

输出 #1

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$$$。