[WEEK 02]アルゴリズム-優先キュー問題を解く

11279.最大お尻
https://www.acmicpc.net/problem/11279
まず、heapqライブラリで書かれたコードはもちろんタイムアウトしました.

import sys

input = sys.stdin.readline

N = int(input())

lst = [int(input().split('\n')[0]) for _ in range(N)]
arr = []

for x in lst:
    if x == 0:
        if len(arr) == 0:
            print(0)
        else:
            print(max(arr))
            arr.remove(max(arr))
    else:
        arr.append(x)

次はheapqライブラリを使用した答えコードです.

import sys
import heapq

sys.stdin = open("5-1_11279.txt", "r")
input = sys.stdin.readline

N = int(input())
heap = []

for _ in range(N):
    num = int(input())
    if not num:
        # 힙이 비어 있지 않으면 최대값 출력
        if heap:
            print(-(heapq.heappop(heap)))
        # 힙이 비어 있으면 0 출력
        else:
            print(0)
    else:
        heapq.heappush(heap, -num)

heapq.heappush(heap, item)
Push the value item onto the heap, maintaining the heap invariant.
heapq.heappop(heap)
Pop and return the smallest item from the heap, maintaining the heap invariant. If the heap is empty, IndexError is raised. To access the smallest item without popping it, use heap[0].
heapqライブラリのheappush()は、最大のhipではなく最小のhipをサポートします.したがって、入力値に−(heappush,−cmd)を乗算し、出力時に−を乗算すると、最大hip(-(heapq.heapppop(heapp))が得られる.
1655.真ん中を言う
https://www.acmicpc.net/problem/1655
問題では,与えられた「数の個数が偶数であれば,中間の2つの数に小数を出すべきである」という条件が,その問題を解くための核心条件である.
小さな入力値を格納する最大hip-left heapと、大きな入力値を格納する最小hip-right heapを作成することで、left heapの0番目の要素(ルートノードも最大値)を出力します.

import sys
import heapq

input = sys.stdin.readline

N = int(input())

# left_heap: 최대 힙 / right_heap: 최소 힙
left_heap = []
right_heap = []

# 수빈이가 외친 값 입력
for i in range(N):
    num = int(input())
    # left_heap과 right_heap에 번갈아 가며 입력값을 추가
    if i % 2 == 0:
        # 작은 값들이 저장된 left_heap에서 필요한 값은 최댓값이므로 최대 힙
        heapq.heappush(left_heap, -num)
    else:
        # 큰 값들이 저장된 right_heap에서 필요한 값은 최솟값이므로 최소 힙
        heapq.heappush(right_heap, num)
    
    # 만약 left_heap에서 right_heap보다 큰 값이 저장되었으면 바꿔준다.
    if right_heap and -left_heap[0] > right_heap[0]:
        heapq.heappush(left_heap, -heapq.heappop(right_heap))
        heapq.heappush(right_heap, -heapq.heappop(left_heap))
    
    print(-left_heap[0])

11279題に示すように、最大臀部は−値であり、入出力である.
1715.整列カード
https://www.acmicpc.net/problem/1715
カード群の総比較回数を最大限に減らすには、小さなカード群から、大きなカード群の順に比較しなければならない.小さなグループでソートするには、要素の最小ヒップを昇順でソートします.

import sys
import heapq

input = sys.stdin.readline

N = int(input())
heap = []
heapq.heapify(heap)

for i in range(N):
    heapq.heappush(heap, int(input()))

answer = 0

while len(heap) > 1:
    num1 = heapq.heappop(heap)
    num2 = heapq.heappop(heap)
    sum = num1 + num2
    answer += sum
    heapq.heappush(heap, sum)
    
print(answer)

最大値または最小値を求める問題ではhipを使用することが望ましい.