[백준 29336] 월향, 비상 (C++)

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

문제

---

월간 향유회(이하 월향)의 운영진들은 고민에 빠졌다. 당장 이번 달 대회에 출제할 문제가 부족하기 때문이었다. 위기의 대회를 구할 마지막 희망, 박신욱은 운영진들이 힘을 합쳐 문제를 만들 것을 제안하였다.

문제를 만들기 시작한 0일 째에 운영진 𝑁명의 역량은 각각 𝐴_𝑖와 같다. 월향의 운영진들은 성장하는 인재이므로 하루가 지날 때마다 역량이 1씩 늘어난다. 운영진들은 본인의 역량에 준하는 퀄리티의 문제를 만들거나, 본인의 역량만큼 기존 문제 중 하나의 퀄리티를 높일 수 있다. 문제를 만들거나 기존 문제의 퀄리티를 높이는 데에는 시간이 걸리지 않는다. 단, 한 번 대회에 기여한 운영진은 힘들어서 더 이상 대회에 기여할 수 없다.

대회가 원활하게 준비되기 위해서는 진행 상황이 점차 진척되어야 한다. 이는 𝑀개의 조건으로 표현할 수 있다.

•  𝑇_𝑖일까지 만들어진 문제들의 퀄리티의 합이 𝑄_𝑖 이상이어야 한다.

월향의 운영진들이 조건을 모두 만족하면서 최적으로 문제를 만들었을 때, 마지막 조건이 있는 날까지 만들어진 문제들의 최대 퀄리티 합을 구하여라.

 

입력

---

첫째 줄에 운영진의 수 𝑁과 조건의 수 𝑀이 공백으로 구분되어 주어진다. (1 ≤ 𝑁, 𝑀 ≤ 200 000)

둘째 줄에 각 운영진의 역량을 뜻하는 𝑁개의 정수 𝐴₁, 𝐴₂, ⋯, 𝐴_𝑁이 공백으로 구분되어 주어진다. (1 ≤ 𝐴_𝑖 ≤ 10⁹)

셋째 줄부터 𝑀개의 줄에 각 조건을 나타내는 두 정수 𝑇_𝑖, 𝑄_𝑖가 공백으로 구분되어 주어진다. (1 ≤ 𝑇_𝑖, 𝑄_𝑖 ≤ 10⁹)

배열 𝑇와 𝑄는 각각 오름차순으로 주어진다.

출력

---

모든 조건을 만족하도록 문제를 만들었을 때, 마지막 조건의 날까지 만들어진 문제들의 퀄리티의 합으로 가능한 최댓값을 출력한다. 만약 문제를 어떻게 만들어도 모든 조건을 만족할 수 없다면 대신 -1을 출력한다.

 

문제 풀이

---

그리디 문제.

하루마다 운영진들의 역량이 1씩 늘어나므로, 최대한 사람을 많이 남기면서 대회에 기여하는 것을 미뤄야 한다. 따라서 M개의 각 조건의 날짜 날에 가장 역량이 뛰어난 사람부터 차례로 문제를 만들거나 기존 문제의 퀄리티를 높이면 된다. 가장 역량이 뛰어난 사람이 대회에 기여했는데도 Q_i 보다 작다면 다음으로 역량이 뛰어난 사람, 그러고도 Q_i보다 작다면 그 다음으로 역량이 뛰어난 사람... 순으로 대회에 기여하면 된다.

내림차순으로 정렬된 우선순위 큐에 운영진들의 0일차 역량을 저장하고, T_i마다 Q_i를 넘기는지 확인한다. T_i 날에 가장 역량이 뛰어난 사람의 역량은 pq.top() + T_i가 된다. Q_i보다 크거나 같을 때까지 해당 값을 현재까지 문제의 퀄리티에 더한다.

마지막 조건의 날에는 기여하지 못한 사람이 없도록 큐를 비워준다. 이 방법이 문제의 퀄리티 합의 최댓값을 구하는 방법이므로 해당 방법으로 모든 사람이 대회에 기여했는데 Q_M-1보다 문제 퀄리티가 낮다면 -1을 출력해주면 된다.

 

아래는 코드.

#include <iostream>
#include <queue>
#include <utility>
using namespace std;

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int N, M;
	int quality;
	long long currentQuality = 0;
	cin >> N >> M;
	priority_queue<int, vector<int>, less<int>> q;
	pair<int, int>* conditions = new pair<int, int>[M];
	for (int i = 0; i < N; i++)
	{
		cin >> quality;
		q.push(quality);
	}
	for (int i = 0; i < M; i++)
	{
		cin >> conditions[i].first >> conditions[i].second;
	}
	for (int i = 0; i < M; i++)
	{
		while (!q.empty() && currentQuality < conditions[i].second)
		{
			int currentBest = q.top();
			q.pop();
			currentQuality += currentBest + conditions[i].first;
		}
	}
	while (!q.empty())
	{
		currentQuality += q.top() + conditions[M - 1].first;
		q.pop();
	}
	if (currentQuality >= conditions[M - 1].second)
	{
		cout << currentQuality << "\n";
	}
	else
	{
		cout << -1 << "\n";
	}
	return 0;
}