17612 쇼핑몰

Link

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

Detail

문제에 적힌 내용을 그대로 시뮬레이션 해보는 과정에서 “빨리 끝난 계산대부터” 손님을 보내서 계산하고, 마지막 정답도 “먼저 계산이 끝난 순서대로” 처리한다는 내용에서 [우선순위 큐](Priority Queue) 를 사용하면 $Nlog(N)$ 으로 시간 내에 풀 수 있다고 생각되었다.

세 개의 자료구조

Waiting

vector<pair<int, int>> waiting

대기열에 서있는 손님들의 목록을 배열에 저장한다.

Cashiers

// {last_time, number}  
priority_queue<  
    pair<int, int>,  
    deque<pair<int, int>>,  
    greater<>  
> cashiers;

{계산이 끝날 시각, 계산대의 번호} 를 오름차순으로 저장하는 우선순위 큐다. 여기에 매번 손님이 계산하러 갈 때마다 last_time을 갱신시켜 top에 항상 다음 계산대가 위치하도록 한다. “두 계산기가 모두 계산가능할경우, 번호가 작은 순서대로 손님을 배정한다” 라는 규칙에 위배되지 않도록 구조가 짜여있다.

finish_quque

priority_queue<  
       tuple<int, int, int>,  
       vector<tuple<int, int, int>>,  
       greater<>  
> finish_queue;  

{계산이 끝난 시각, -계산대 번호, 손님 id} 순서로 저장하는 우선순위 큐다. 계산이 끝난 순서대로 확인하되, 시간이 같은 경우에 계산대 번호가 큰 손님부터 정답에서 계산해야 하므로 계산대 번호에 -1을 곱하여 두번째 요소로 넣어서 연산한다.

Code

#include<bits/stdc++.h>  
  
using namespace std;  
typedef long long ll;  
  
int main() {  
    int n, k;  
    cin >> n >> k;  
  
    // {id, time}  
    vector<pair<int, int>> waiting;  
  
    // {last_time, number}  
    priority_queue<  
       pair<int, int>,  
       deque<pair<int, int>>,  
       greater<>  
    > cashiers;  
  
    // { finish_time, -cashier_id, customer_id }  
    priority_queue<  
       tuple<int, int, int>,  
       vector<tuple<int, int, int>>,  
       greater<>  
    > finish_queue;  
  
  
    // init  
    // customers    
    for (int i = 0; i < n; i++) {  
       int id, duration;  
       cin >> id >> duration;  
       waiting.emplace_back(id, duration);  
    }  
  
    // simulation  
  
    // first k customers    
    for (int cashier_id = 0; cashier_id < k; cashier_id++) {  
       cashiers.emplace(0, cashier_id);  
    }  
  
  
    for (int i = 0; i < n; i++) {  
       auto [id, duration] = waiting[i];  
       auto [last_time, number] = cashiers.top(); cashiers.pop();  
  
       int finish_time = last_time + duration;  
       finish_queue.emplace(finish_time, -number, id);  
       cashiers.emplace(finish_time, number);  
    }  
  
    ll r = 1;  
    ll answer = 0;  
    while (not finish_queue.empty()) {  
       auto [finish_time, cashier_id, customer_id] = finish_queue.top(); finish_queue.pop();  
  
       //cout << finish_time << " " << cashier_id << " " << customer_id << endl;  
  
       answer += (r++) * (ll)customer_id;  
    }  
  
    cout << answer << endl;  
  
}