백준 32143 - 카드 게임 (Hard) (C++)

문제

• 문제 링크

  
   BOJ 32143 - 카드 게임 (Hard) 
  

• 문제 요약

$N$개의 공격 카드 $D_1, D_2, ... , D_N$에 대해 $Q$번에 걸쳐 추가 공격 카드가 주어진다.
쿼리마다 공격 카드를 최대한 적게 사용해 $H$를 $0$ 이하로 줄이려할 때, 목표를 달성하기 위한 가능성을 판별하라.



• 제한

TL : $1$ sec, ML : $1024$ MB




$1 ≤ N, Q ≤ 3 \times 10^5$

$1 ≤ H, D_i, x ≤ 10^9$

알고리즘 분류

• 자료 구조 (Data Structures)
• 그리디 알고리즘 (Greedy)
• 우선순위 큐 (Priority Queue)

풀이

임의의 쿼리에서, 수중에 공격 카드 $D_1, D_2, ... , D_i$를 가지고 있다고 해보자. 이들을 이용해 $H$를 $0$ 이하로 줄일 수 있다면, 이것이 가능한 선에서 공격 카드를 최대한 줄여내야만 한다.

공격 카드를 줄일 때는 당연하게도 $D_i$가 작은 녀석들부터 차례로 쳐내는 것이 최선이다.

한편, 문제의 제한이 $1 ≤ N, Q ≤ 3 \times 10^5$이므로 $D_i$가 작은 녀석들을 나이브하게 찾아주기엔 무리가 있다.

이에 따라 삽입, 삭제, $min(D_i)$를 $O(logN)$에 관리할 수 있게 해주는 $min$ $heap$을 이용해 주자.

추가로 $heap$에 들어있는 요소들의 합을 담을 변수도 함께 관리해 주는 것이 편하다.

전체 코드

#include<bits/stdc++.h>
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int h, n, q; cin >> h >> n >> q;
 
    priority_queue <int, vector <int>, greater<int>> pq;
    long sum{};
    while(n--)
    {
        int x; cin >> x;
        pq.push(x);
        sum += x;
    }
 
    do
    {
        while(sum - pq.top() >= h)
        {
            sum -= pq.top();
            pq.pop();
        }
 
        cout << (sum < h ? -1 : (int)pq.size()) << '\n';
 
        int x; cin >> x;
        pq.push(x);
        sum += x;
    } while(q--);
}

comment

끝