[백준 17612] 쇼핑몰

문제

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

 

알고리즘

Priority queue

 

풀이

문제에서 정의한 계산 순서를 구하는 문제입니다.

 

우선순위 큐를 이용한 구현문제에 가깝습니다. 빈 계산대가 여러 개 있다면 번호가 작은 계산대부터 계산해야 하므로 빈 계산대를 저장하는 $counter$변수, $info$ 클래스를 정의하여 각 아이디와 계산시간 및 카운터 정보를 기록하고 해당 클래스 객체의 우선순위를 위한 $compareInfo$ 클래스를 정의합니다.

 

다만, 우선순위큐를 통해 카운터에서 계산될 순서를 저장하게 될 때, 가장 빠르게 계산이 끝나는 $info$ 객체를 우선순위 큐에서 뽑았다면, 나머지 우선순위 큐 안에 있는 $info$ 객체의 $time$ 변수 또한 업데이트를 모두 해주어야 합니다. 우선순위 큐 안에 있는 모든 객체들의 $time$을 갱신하는 대신, 새로이 계산할 $info$객체의 시간을 늘려줌으로써 상대적으로 우선순위 큐 안에 있는 시간이 갱신되도록 하였습니다.

 

코드

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 1; i <= n; ++i)
using namespace std;

int N, K, kth, cur, idx;
long long ans;

class info {
public:
    int id, time, ct;
    info(int _id, int _time, int _ct) : id(_id), time(_time), ct(_ct) {}
};
class compareInfo {
public:
    bool operator()(const info& a, const info& b) {
        if (a.time == b.time) return a.ct < b.ct;
        return a.time > b.time;
    }
};

void solve(int _id) {
    ++kth;
    ans += (long long)kth * _id;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);

    cin >> N >> K;
    vector<info> line;
    priority_queue<info, vector<info>, compareInfo> pq;
    priority_queue<int, vector<int>, greater<int>> counter;

    rep(i, N) {
        int id, cnt;
        cin >> id >> cnt;
        if (i >= K) line.emplace_back(info(id, cnt, i));
        if (i < K) pq.emplace(info(id, cnt, i));
    }

    while (!pq.empty()) {

        while (!pq.empty() && (pq.top().time == cur)) {
            auto [id, time, ct] = pq.top();
            pq.pop();
            counter.emplace(ct);
            solve(id);
        }

        while (!counter.empty() && (idx < N - K)) {

            int nextCounter = counter.top();
            counter.pop();
            auto [id, time, ct] = line[idx++];
            pq.emplace(info(id, cur + time, nextCounter));
        }

        ++cur;
    }
    cout << ans;
    return 0;
}