[BOJ 1202]ジュエリー泥棒

6774 ワード
テキストリンク
大体のアルゴリズムは
1.宝石とリュックサックは重量順
2.1パックに入れる宝石の中で、一番高い宝石を選ぶ
はい.
N,K<=300000、O(NK)O(NK)O(NK)なので時間を減らす方法を考えています.
第2段階で考えると、前のバッグに入ることができる宝石はもちろん次のバッグに入ることもできます.(バッグの重さも昇順に並べられています)入れた宝石を再確認する必要はありません.
また、最も高い宝石を選ぶには、並べ替えが必要な問題があります.使用우선순위 큐一番高い宝石はO(1)O(1)O(1)だけで見つけられます.
・67917・宝石とリュックサックの並び替え->O、O、O、O、O、O、O
  • バックパックツアー->O(K)O(K)
    2.1各パッケージの優先順位キューに宝石価格->O(logn})O(logn)、67918、
    最終時間複雑度:最大時間複雑度:O、O、O、O、O、O
    import sys
sys.stdin = open('input.txt', 'r')
sys.setrecursionlimit(int(1e5))
input = sys.stdin.readline

import heapq

N, K = map(int, input().split())
jems = []
for _ in range(N):
    m, v = map(int, input().split())
    jems.append([m, v])
bags = []
for _ in range(K):
    bags.append(int(input()))

# 무게를 기준으로 오름차순 정렬
jems.sort()
bags.sort()

pq = []
jem = 0 # 보석 인덱스
answer = 0
for i in range(len(bags)):
    # i번째 가방에 넣을 수 있는 보석 모두 넣기
    # 후보 pq에 넣으면 보석 인덱스 증가
    # pq는 min-heap이므로 (-)를 곱해서 push
    while jem < len(jems) and jems[jem][0] <= bags[i]:
        heapq.heappush(pq, -jems[jem][1])
        jem += 1
    
    # 후보들 중에서 가격이 가장 높은 보석 1개 선택
    if len(pq):
        answer += -heapq.heappop(pq)

print(answer)
    • ラビリンス脱出[bfs]
    [JS関数]即時実行関数