P6979: 最小化干草捆
传统题
4.000s
时间限制
512MB
内存限制
5 提交
4 解决
【题目描述】
【题目描述】
Bessie
感到无聊，于是又在 Farmer John 的牛棚里制造麻烦。FJ 有 N (1≤N≤10
^5)
堆草堆。对于每个 i∈[1,N]，第 i
堆草堆有 hi（1≤hi≤10
^9
）的草。Bessie
不想让任何的草倒下来，所以她唯一可以执行的操作为：
l
如果两个相邻的草堆的高度相差不超过 K
（1≤K≤10
^9
），她可以交换这两堆草堆。
Bessie
在一系列这样的操作之后可以得到的的字典序最小的高度序列是什么？
**注意：本题的时间和内存限制分别为 4 秒和 512MB，通常限制的两倍。**
【
输入格式】
（从终端 /
标准输入读入）：
输入的第一行包含 N
和 K。第 i+1
行包含第 i 堆草堆的高度。
【
输出格式】
（输出至终端 /
标准输出）：
输出 N
行，第 i 行包含答案中第 i 堆草堆的高度。
【
输入样例】
：
5 3
7
7
3
6
2
【
输出样例】
：
6
7
7
2
3
【样例说明】
一种 Bessie
可以交换草堆的方式如下：
7 7 3 6 2
-> 7 7 6 3 2
-> 7 7 6 2 3
-> 7 6 7 2 3
-> 6 7 7 2 3
【
测试点性质】
：
所有测试点的 10%
满足 N≤100。
所有测试点的另外 20%
满足 N≤5000。
其余 70%
的测试点没有额外限制。