[白俊]2075:N 2番目の数字
825 ワード
優先キュー
N番目の大数
メモリ制限は12 MBと非常に小さい.
質問では「埋めた数に特徴があり、すべての数が自分の1つの格の数よりも大きい」というので、低票を90度回転して並べ替え、優先順位キューに入れて解くだけでいいと思いますが、メモリの制限は非常に小さいと思います.
この問題はコンセントの問題のように、5個を超えると6番目の大きな数字が捨てられるのが問題の核心です.
残りは優先順位キューとほぼ同じで,ひっくり返す必要がなくこの問題を解決できる.import sys
import heapq
input = sys.stdin.readline
n = int(input())
lst = []
for i in range(n):
lst.append(list(map(int, input().split())))
result = []
for i in lst:
for j in i:
# minHeap
heapq.heappush(result, j)
# 5개가 넘어가면 젤 작은 수부터 버려!
if len(result) > n:
heapq.heappop(result)
# 가장 작은 수부터 5개 있으니 가장 작은수 출력
print(result[0])
Reference
この問題について([白俊]2075:N 2番目の数字), 我々は、より多くの情報をここで見つけました
https://velog.io/@jinii/백준-2075-N번째-큰-수
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
import sys
import heapq
input = sys.stdin.readline
n = int(input())
lst = []
for i in range(n):
lst.append(list(map(int, input().split())))
result = []
for i in lst:
for j in i:
# minHeap
heapq.heappush(result, j)
# 5개가 넘어가면 젤 작은 수부터 버려!
if len(result) > n:
heapq.heappop(result)
# 가장 작은 수부터 5개 있으니 가장 작은수 출력
print(result[0])
Reference
この問題について([白俊]2075:N 2番目の数字), 我々は、より多くの情報をここで見つけました https://velog.io/@jinii/백준-2075-N번째-큰-수テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol