시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 1484 | 722 | 555 | 57.812% |
힙은 자료의 추가, 우선순위가 제일 높은 자료의 삭제가 가능한 자료구조이다. 이와 같은 힙에는 두 종류가 있는데, 각각 최소-힙, 최대-힙이다. 이 문제에서는 최대-힙을 다루기로 하자.
이와 같은 최대-힙을 이용하면 O(n log n)정렬인 힙 정렬을 할 수 있다. 우리가 다루기로 한 최대-힙을 이용하면 오름차순 정렬을 할 수 있다. 힙 정렬은 크게 두 개의 단계로 나뉘는데, 첫 번째 단계는 주어진 자료들로 힙을 구성하는 단계이고, 두 번째 단계는 이렇게 구성된 힙에서 최댓값을 계속 제거하는 단계이다.
예를 들어 (5, 4, 2, 1, 3)과 같은 힙을 살펴보자. 이 힙에서 최댓값을 삭제하면 (3, 4, 2, 1)이 되고, 힙의 조건을 맞추기 위해 Swap을 한 번 하면 (4, 3, 2, 1)의 힙을 얻는다. 이 힙에서 최댓값을 삭제하면 (1, 3, 2)이 되고, 힙의 조건을 맞추기 위해 Swap을 한 번 하면 (3, 1, 2)가 된다. 다음 단계에서는 (2, 1), (1)이 되고 힙 정렬이 종료된다. 즉, 힙이 (5, 4, 2, 1, 3)과 같이 구성되어 있었다면, 정렬을 위해 Swap을 두 번 사용하게 된다. 하지만 (5, 4, 3, 2, 1)과 같은 힙은 총 네 번의 Swap을 해야 한다.
n이 주어졌을 때, 1부터 n까지의 수를 한 번씩 사용하여 만들 수 있는 힙들 중에서, 위와 같은 Swap 회수가 최대가 되도록 하는 힙을 출력하는 프로그램을 작성하시오.
첫째 줄에 n이 주어진다. (1 ≤ n ≤ 100,000)
첫째 줄에 n개의 정수로 힙을 출력한다.
6
6 5 3 2 4 1
5
5 4 3 2 1
ICPC > Regionals > Northern Eurasia > Northern Eurasia Finals > NEERC 2004 H번