[BOJ] 24041번 : 성싶당 밀키트 C++ 풀이

이분탐색 + 우선순위 큐 자료구조를 사용해야하는 문제이다.
N개의 재료중 Oi가 1인 재료 K개를 제외했을때, 세균의 합이 G이하라면 먹을 수  있다. 이때 최대 유통기한을 얼마나 만들 수 있을까?

문제를 보자마자 이분탐색인걸 파악했다. mid로 날짜를 대입해보면서 만족하는 최대 mid를 구하면 되겠다 싶었다.

그러면 K개를 어떻게 선정할까? 그리디하게 생각해보고 싶지만, Si * max(1, x - Li)를 항상 보장할 수는 없다. 그래서 우선순위 큐에 현재까지 뽑은 재료 K개를 유지하도록 접근해봤다. mid를 이용해 모든 세균의 합을 구하고, 마지막에 우선순위 큐에서 K개의 재료로 인해 발생한 세균을 빼주면 간단하게 구할 수 있다.

날짜는 최대 20억이 가능하므로 left = 1, right = 2e9로 잡아주면 되고, 시간복잡도는 O(N log 2e9 + K log 2e9)이 소요된다.

#include <bits/stdc++.h>
#define MINF 0x7f7f7f7f
#define INF 1000000000
#define MOD 1000000009
#define NUM 200010
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
int N, G, K, answer = 0;
bool isPossible[NUM];
vector<pll> v;
priority_queue<pll> pq;

void init() {
    memset(isPossible, false, sizeof(isPossible));
    cin >> N >> G >> K;
    for (int i=1; i<=N; i++) {
        ll x, y, z;
        cin >> x >> y >> z;
        if (z == 0) isPossible[i] = true;
        v.push_back({x, y});
    }

    ll left = 0, right = 4000000000;
    while (left <= right) {
        ll mid = (left + right) / 2;
        ll res = 0;
        for (int i=0; i<N; i++) {
            ll num = v[i].X * max((ll)1, mid - v[i].Y);
            res += num;
            if (isPossible[i+1]) continue;
            if (pq.size() < K) {
                pq.push({-num, i+1});
            } else if (!pq.empty() && -pq.top().X < num){
                pq.pop();
                pq.push({-num, i+1});
            }
        }
        while (!pq.empty()) {
            res += pq.top().X;
            pq.pop();
        }
        if (res <= G) {
            answer = mid;
            left = mid + 1;
        } else right = mid - 1;
    }
    cout << answer << '\n';
} 




int main(){
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    init();
}