[BOJ] 백준 1202 보석 도둑

문제 링크

www.acmicpc.net/problem/1202

1202번: 보석 도둑

 

풀이

보석이 N개, 가방이 K개 있습니다. 각 가방은 담을 수 있는 최대 무게가 정해져있고, 하나의 보석만을 담을 수 있습니다.

 

그리디하게 생각합시다. 최대 무게가 작은 가방부터 보며 그때 담을 수 있는 최대 가치의 보석을 털면 됩니다.

증명은 BOJ 채점기가 해주겠죠??

자세한 구현은 코드를 참고해주세요.

 

정답 코드

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f
#define ft first
#define sd second
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vb = vector<bool>;
using vs = vector<string>;
using vd = vector<double>;
using vll = vector<ll>;
using vpii = vector<pii>;
using vvi = vector<vi>;
using vvb = vector<vb>;
using vvll = vector<vll>;
using vvpii = vector<vpii>;

int n, k;
pii p[333'333];
int bag[333'333];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> p[i].ft >> p[i].sd;
    }
    for (int i = 0; i < k; i++) {
        cin >> bag[i];
    }
    p[n] = {INF, 0};
    n++;
    sort(bag, bag + k);
    sort(p, p + n);
    int idx = 0;
    priority_queue<int> q;
    ll ans = 0;
    for (int i = 0; i < n && idx < k;) {
        if (p[i].ft <= bag[idx]) {
            q.push(p[i++].sd);
            continue;
        }
        while (idx < k && bag[idx] < p[i].ft) {
            if (!q.empty()) {
                ans += q.top();
                q.pop();
            }
            idx++;
        }
    }
    cout << ans;
}