문제
배씨에게 N(1≤N≤105)개의 건초 더미가 있는데, 각 i∈[1, N]번째 건초 더미는 hi(1≤hi≤109)의 높이를 가지고 있다.
배씨는 인접한 두 건초 더미의 높이가 최대 K(1≤K≤109)이하 차이가 나는 경우 두 건초 더미를 교환할 수 있다.
배씨가 이러한 일련의 교환 작업을 수행한 후 얻을 수 있는 사전순 최소 수열(lexicographically minimum sequence)를 출력하자.
사전순 최소 수열은 구할 수 있는 모든 수열 중 가장 사전순으로 정렬된 형태의 수열이다.
입력
첫 번째 줄에는 N과 K가 입력된다.
두 번째 줄부터 N줄에 걸쳐 i+1 번째 줄에는 i 번째 건초 더미의 높이가 입력된다.
출력
i 번째 건초 더미의 높이를 i 번째 줄에 출력하시오.
예제1
입력
5 3
7
7
3
6
2
출력
6
7
7
2
3
힌트
배씨가 건초 더미를 교환할 수 있는 한 가지 방법은 다음과 같습니다.
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
출처
USACO 2022 January Platinum
로그인해야 코드를 작성할 수 있어요.