#PU1188. USACO 2022 January Contest, Platinum — Problem 1. Minimizing Haybales
USACO 2022 January Contest, Platinum — Problem 1. Minimizing Haybales
USACO 2022 January Contest, Platinum — Problem 1. Minimizing Haybales
题目描述
Bessie is bored and yet again causing trouble in Farmer John's barn. FJ has () stacks of haybales. For each , the th stack has () haybales. Bessie does not want any haybales to fall, so the only operation she can perform is as follows: If two adjacent stacks' heights differ by at most (), she can swap the two stacks. What is the lexicographically minimum sequence of heights that Bessie can obtain after some sequence of these operations? Note: the time and memory limits for this problem are 4s and 512MB, twice the defaults.
输入格式
The first line of input contains and . The -st line contains the height of the -th haybale.
输出格式
Please print out lines, the -th containing the height of the -th haybale in the solution.
数据范围
In 10% of all input cases, In another 20% of all input cases, In the remaining 70% of input cases, there are no additional Problem credits: Daniel Zhang and Benjamin Qi
样例
样例 1
5 3
7
7
3
6
2
6
7
7
2
3
One way that Bessie can swap the stacks is as follows:
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