백준 1202 보석 도둑
이 문제의 알고리즘은 다음과 같다.
1. 보석의 가격을 1순위로 해서 가격과 무게를 내림차순 정렬을 한다
2. set에 가방의 최대 무게들을 담는다.
3. set의 lower_bound 함수를 이용해서 각 보석의 무게를 감당할 수 있는 최소한의 가방을 선택한다.
ex) 3 2
1 65
5 23
2 99
10
2
보석의 무게가 2일 때 , lower_bound에 넣으면 10이 아닌 최대 2의 무게를 가질 수 있는 가방이 선택된다.
#include <bits/stdc++.h>
#include<set>
using namespace std;
int n, k;
vector<pair<int,int>> v;
multiset<int> s;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> k;
while (n--) {
int a, b;
cin >> a >> b;
v.push_back({ b,a });
}
sort(v.begin(), v.end(),greater<>());
while (k--) {
int x;
cin >> x;
s.insert(x);
}
long long ans = 0;
for (auto c : v) {
if (s.empty()) break;
if (s.lower_bound(c.second) == s.end()) continue;
else ans += c.first;
s.erase(s.lower_bound(c.second));
}
cout << ans << '\n';
}
Author And Source
이 문제에 관하여(백준 1202 보석 도둑), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@supway/백준-1202-보석-도둑저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)