문제
https://www.acmicpc.net/problem/1781
문제해설
N개의 문제가 주어지고 문제를 풀면 컵라면을 받을 수 있다.
문제에는 데드라인과 받을 수 있는 컵라면의 개수가 주어진다.
문제를 푸는데는 1시간이 걸리고
데드라인 내에만 해당 문제를 풀 수 있다.
문제풀이
벡터에 문제를 넣고 데드라인 기준으로 오름차순 정렬을 해준다.
정렬된 문제를 앞에서부터 보면서
우선순위 큐의 크기(현재 시간)보다 작다면 큐에 넣어준다.
그렇지 않다면 우선순위 큐의 top의 수(컵라면의 수)와 현재 컵라면의 수를 비교해준다.
현재 컵라면의 수가 더 크다면 top을 빼주고 현재 컵라면을 넣어준다.
가장 많은 컵라면을 만들기 위해서이다.
위의 과정을 거치면 큐 안에는 최대의 수를 만들기 위한 컵라면만 들어있게 된다.
큐에서 하나씩 빼주며 합을 계산해주면 정답이다.
전체코드
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
33
34
35
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
typedef pair<int, int>P;
int main() {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int n; cin >> n;
vector<P>arr(n);
for (int i = 0; i < n; i++)
cin >> arr[i].first >> arr[i].second;
sort(arr.begin(), arr.end());
priority_queue<int, vector<int>, greater<int>>pq;
for (int i = 0; i < n; i++) {
if (pq.size() < arr[i].first) {
pq.push(arr[i].second);
}
else {
if (pq.top() < arr[i].second) {
pq.pop();
pq.push(arr[i].second);
}
}
}
int sum = 0;
while (!pq.empty()) {
sum += pq.top();
pq.pop();
}
cout << sum;
return 0;
}