白駿11279号:最大お尻
質問する https://www.acmicpc.net/problem/11279 最大ヒップホップ を実現
きろくてん
記録最大ヒップホップ実現 は、問題の解答とは無関係であっても、関連関数を一緒に記録する.
方法
参考 ITA書籍、最大実現可能HIP 回答の提出
きろくてん
記録
参考
def parent(i):
return (i-1)//2
def left(i):
return i*2 + 1
def right(i):
return i*2 + 2
def heapify(arr, i):
l, r = left(i), right(i)
largest = i
if l < len(arr) and arr[l] > arr[largest]:
largest = l
if r < len(arr) and arr[r] > arr[largest]:
largest = r
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, largest)
def build_heap(arr):
parent_end = len(arr)//2 - 1
for i in range(parent_end, -1, -1):
heapify(arr, i)
def get_max(heap):
return heap[0]
def extract_max(heap):
L = len(heap)
if L < 1:
return False
max_value = heap[0]
heap[0] = heap[L-1]
heap.pop()
heapify(heap, 0)
return max_value
def increase(heap, i, v):
if v < heap[i]:
return False
heap[i] = v
while i > 0:
p = parent(i)
if heap[p] >= heap[i]:
break
heap[p], heap[i] = heap[i], heap[p]
i = p
def insert(heap, v):
heap.append(v)
i = len(heap) - 1
while i > 0:
p = parent(i)
if heap[p] >= heap[i]:
break
heap[p], heap[i] = heap[i], heap[p]
i = p
import sys
N = int(sys.stdin.readline())
heap = []
for i in range(N):
todo = int(sys.stdin.readline())
if todo == 0:
# 힙에서 가장 큰 값을 출력
v = extract_max(heap)
print(v or 0)
else:
# 힙에 자연수 추가
insert(heap, todo)
Reference
この問題について(白駿11279号:最大お尻), 我々は、より多くの情報をここで見つけました https://velog.io/@johnny/beak-11279テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol