티스토리 뷰

알고리즘 관련/BOJ

BOJ)1202 보석 도둑

JASON 자손9319 2017. 4. 12. 15:04

문제: icpc.me/1202


가장 가격이 많이 나가는 보석을 최대한 많이 담아야 원하는 답을 구할 수 있는건 그리디하게 알 수 있다.


그렇기 때문에 우리는 가장 가격이 많이 나가는 보석을 먼저 보며 lower_bound를 이용하여 현재 그 보석을 담을 수 있는 가방이 있느지 확인해주면 된다.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <cstdio>
#include <algorithm>
#include <queue>
#include <set>
using namespace std;
int n, k, x, y;
long long r;
int main() {
    scanf("%d%d"&n, &k);
    priority_queue<pair<intint>> pq;
    for (int i = 0; i < n; i++) {
        scanf("%d%d"&x, &y);
        pq.push({ y,x });
    }
    multiset<int> ms;
    for (int i = 0; i < k; i++) {
        scanf("%d"&x);
        ms.insert(x);
    }
    while (pq.size()) {
        int cost = pq.top().first;
        int pay = pq.top().second;
        pq.pop();
        auto it = ms.lower_bound(pay);
        if (it == ms.end())
            continue;
        ms.erase(it);
        r += cost;
    }
    printf("%lld\n", r);
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)2820 자동차 공장  (0) 2017.04.13
BOJ)7573 고기잡이  (0) 2017.04.12
BOJ)1202 보석 도둑  (0) 2017.04.12
BOJ)14499 주사위 굴리기  (2) 2017.04.12
BOJ)2213 트리의 독립집합  (1) 2017.04.10
BOJ)3770 대한민국  (0) 2017.04.06
TAG
,
댓글
댓글쓰기 폼