백준 28339 이상한 드래프트

문제

https://www.acmicpc.net/problem/28339

28339번: 이상한 드래프트

풀이

이런 문제는 idx가 0부터 K-1까지를 순수하게 구하고.

idx를 1부터 N-K까지 이동시키면서 필요한 데이터를 갱신하면 풀 수 있다.

idx를 idx+1로 이동시키면 idx의 값은 뺴줘야하고, idx+K의 값은 추가시키면 된다.

어차피 다 구해봐야한다.

우리가 알아야 할건

idx이상, idx + K - 1이하의 모든 선수에 대해 각 포지션별로 모든 선수가 있는지, 있다면 각 포지션별 최대값의 합이다.

다행힌건 포지션의 종류는 9종류이다. 포지션별로 모든 선수가 있는지는 별 다른 테크닉 없이 쉽게 알 수 있을 것 같다.

문제는 각 포지션별 최대값이다.

따로 posi = [ [ ] for _ in range(9) ]와 같은 것을 만들어도, 무엇이 최대값인지 알려면 len(posi[p])만큼의 복잡도가 필요하다.

이는 비효율적이다.

확실한건 우리가 관심있는건 제일 큰 값뿐이다. 나머지는 들러리다.

이럴땐 우선순위큐가 유용하게 생긴다. 우선순위큐의 0번째 원소는 우선순위가 제일 높은걸 알려준다. 삽입해도 logN의 복잡도이다.

이제 고민할건 우선순위큐의 원소를 삭제하는 것이다. idx~idx+K-1의 값을 계산할때 인덱스가 idx-1이하인 값은 필요없다.

이럴땐 우선순위큐에 수비능력Ai뿐만이나리 인덱스도 같이 삽입해준다.

만약에 우선순위큐 0번째원소의 인덱스가 idx-1이하라면 삭제시켜버린다.

계속 삭제하다보면 비거나(포지션에 선수가 없다) 아니면 원하는 값을 얻을 수 있을 것이다.

 

코드

import math
import sys
from collections import deque
from copy import deepcopy
from heapq import heappush, heappop
from itertools import combinations, permutations

input = sys.stdin.readline
# sys.setrecursionlimit()

for _ in range(int(input())):
    N, K = map(int, input().split())
    data = [tuple(map(int, input().split())) for _ in range(N)]
    ans = 0
    cur = [[] for _ in range(9)]


    def get():
        tmp = 0
        for i in range(9):
            if not cur[i]:
                return 0
            tmp += -cur[i][0][0]
        return tmp


    def adjust(idx):
        for i in range(9):
            while cur[i] and cur[i][0][1] <= idx:
                heappop(cur[i])


    for i in range(K):
        p, a = data[i]
        heappush(cur[p - 1], (-a, i))
    ans = max(ans, get())
    for i in range(K, N):
        # add
        p, a = data[i]
        heappush(cur[p - 1], (-a, i))
        # del
        adjust(i - K)
        ans = max(ans, get())
    print(ans)