백준 1202번 보석 도둑 ( C++ )

문제

https://www.acmicpc.net/problem/1202

 

해설

우선순위 큐와 벡터를 적절히 사용해야하는 문제

시간조건이 까다롭기 때문에 신경써야함

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
 
using namespace std;
 
int n, k, m, v, c;
vector<pair<int, int>> vec;
vector<int> vec2;
priority_queue<int> pq;
long long ret;
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
 
  cin >> n >> k;
  for (int i = 0; i < n; i++)
  {
    cin >> m >> v;
    vec.push_back({m, v});
  }
  sort(vec.begin(), vec.end());
 
  for (int i = 0; i < k; i++)
  {
    cin >> c;
    vec2.push_back(c);
  }
  sort(vec2.begin(), vec2.end());
 
  int j = 0;
  for (int i = 0; i < k; i++)
  {
    while (j < n && vec[j].first <= vec2[i])
      pq.push(vec[j++].second);
    if (pq.size())
    {
      ret += pq.top();
      pq.pop();
    }
  }
 
  cout << ret;
  return 0;
}