문제 풀이

싸지방에 간 준하의 심화 버전인 것 같다.
먼저 우선 순위 큐 두개를 사용하는건 마찬가지. 하나는 계산을 하고 있는 사람들의 정보이고 하나는 계산을 하고 있지 않은 빈 계산대의 정보다.
계산을 하고 있는 사람들의 정보인 pq는 끝나는 시간, 계산대 번호, 회원 번호의 정보를 가지고 있으며 끝나는 시간은 오름 차순(최소 힙), 끝나는 시간이 같으면 계산대 번호 기준으로 내림 차순(최대 힙), 회원 번호는 상관없으므로 그냥 오름 차순으로 cmp함수를 만들었다.

빈 계산대의 정보 pq2는 이 계산대에서 계산을 시작할때 언제 시작하는 것인지의 정보와, 계산대 번호를 가지고 있다.

먼저 계산대에 현재 줄 서 있는 사람들을 모두 채우고 만약에 계산대의 수보다 대기중인 사람이 적으면 있는 만큼만 넣는다.
그리고 while문의 조건에 따라 가장 계산이 일찍 끝나는 사람의 계산을 마치는 시간이 현재 시간보다 작으면 계산을 마쳤다는 의미이므로 pq2에 정보를 넣어준다 (계산을 마치는 시간 = 다음 사람이 계산을 시작하는 시간)
그리고 나서 pq2의 top의 first는 이전 사람이 계산을 끝낸시간 다시 말해서 현재 대기자가 계산을 시작할 시간이고 거기다가 v[i].second(물건의 개수)를 더하면 현재 대기자가 계산을 끝낼 시간이 된다. 이렇게 반복하여 마지막에 pq에 남아 있는 사람들 까지 모두 pop해서 계산을 끝내주면 된다.

문제 링크

boj/17612

소스코드

PS/17612.cpp

#include <string>
#include <vector>
#include<iostream>
#include<memory.h>
#include<map>
#include<algorithm>
#include<queue>
#include<set>
using namespace std;
struct cmp
{
	bool operator()(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b)
	{
		if (a.first.first == b.first.first)
		{
			if (a.first.second == b.first.second)
				return a.second < b.second;
			else
				return a.first.second < b.first.second;
		}
		else
			return a.first.first > b.first.first;
	}
};

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int n,k;
	cin >> n >> k;
	vector<pair<int, int>> v;
	for (int i = 0; i < n; i++)
	{
		int a, b;
		cin >> a >> b;
		v.push_back({a , b});
	}

	priority_queue<pair<pair<int, int>,int>,vector<pair<pair<int, int>, int>>,cmp> pq;
	// 끝나는 시간, 계산대번호, 회원번호
	priority_queue<pair<int,int>,vector<pair<int, int>>,greater<pair<int,int>>> pq2;
	// 시작시간 계산대번호
	int i = 0;
	long long j = 1;
	for (i = 0; i < k; i++)
	{
		if (i >= n)
			break;
		pq.push({ {v[i].second, i}, v[i].first });
	}
	long long ans = 0;
	int now = 0;
	for (; i < n; i++)
	{
		
		while (!pq.empty() && pq.top().first.first <= now || pq.size() >= k)
		{
			now = pq.top().first.first;
			pq2.push({ pq.top().first.first,pq.top().first.second });
			ans += j * pq.top().second;
			j++;
			pq.pop();
		}
		
		pq.push({ {(pq2.top().first + v[i].second),pq2.top().second},v[i].first });
		pq2.pop();
	}
	while (!pq.empty())
	{
		ans += j * pq.top().second;
		j++;
		pq.pop();
	}
	cout << ans;
}