1202번: 보석 도둑
첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci
www.acmicpc.net
각각의 가방마다 최대 한개의 보석만 넣을 수 있으므로
보석들을 가치순으로 정렬하고 해당 보석을 넣을 수 있는 가장 작은 가방에 넣는 식으로 구현했다.
이런 방식으로 구현하면 vector 대신 multiset을 사용해야 시간 초과를 피할 수 있다.
처음에 vector.erase 메서드 인자를 지우는 원소의 인덱스를 받길래 상수시간에 실행될 것이라고 생각했는데
복잡도가 O(n) 였다.
multiset 자료구조를 사용하면 이러한 문제를 피할 수 있다.
더보기
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
using ull = unsigned long long;
struct gem {
ull w, v;
};
bool cmp(gem a, gem b) {
if (a.v == b.v) {
return a.w > b.w;
}
return a.v > b.v;
}
int main()
{
int n, k;
cin >> n >> k;
vector<gem> g(n + 1);
multiset<int> bag;
for (int i = 1; i <= n; i++) {
cin >> g[i].w >> g[i].v;
}
for (int i = 1; i <= k; i++) {
int imsi;
cin >> imsi;
bag.insert(imsi);
}
sort(g.begin() + 1, g.end(), cmp);
ull sum = 0;
g.erase(g.begin());//0
for (int i = 0; i < n; i++) {
auto k = bag.lower_bound(g[i].w);
if (k == bag.end()) continue;
bag.erase(k);
sum += g[i].v;
if (bag.empty()) break;
}
cout << sum;
return 0;
}