Minimizing Haybales

题目描述

Bessie 很无聊，又一次在 Farmer John 的谷仓里惹麻烦。FJ 有 $N$ ($1\leq N \leq 10^5$) 堆干草。对于每个 $i\in [1,N]$，第 $i$ 堆的高度为 $h_i$（$1\le h_i\le 10^9$）个干草包。Bessie 不希望有干草包掉落，因此她唯一能执行的操作如下： 如果两堆相邻干草的高度差不超过 $K$（$1\le K\le 10^9$），她可以交换这两堆。 在进行若干次这样的操作后，Bessie 能得到的高度序列中字典序最小的是哪一个？ 注意：本题的时间与内存限制为 4s 和 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 SCORING: 在全部输入用例的 10% 中，$N\le 100$ 在另外 20% 的输入用例中，$N\le 5000$ 在剩余 70% 的输入用例中，没有额外限制 题目来源：Daniel Zhang 和 Benjamin Qi

标签: USACO|2022|Platinum

来源

USACO|2022|Platinum