KOI 2019 1차 고등부 1번 / 쇼핑몰 - 17612

#include <iostream>
#include <queue>
using namespace std;
 
int N, K;
 
struct Casher {
    int idx;
    int rest;
};
 
struct Mem {
    int mnum;
    int otime;
    int cidx;
};
 
bool operator<(const Casher& c1, const Casher& c2) {
    if(c1.rest == c2.rest) return c1.idx < c2.idx;
    return c1.rest < c2.rest;
}
 
bool operator<(const Mem& n1, const Mem& n2) {
    if(n1.otime == n2.otime) return n1.cidx < n2.cidx;
    return n1.otime < n2.otime;
}
 
priority_queue<Casher> cpq;
priority_queue<Mem> mpq;
 
int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin >> N >> K;
    for(int i = 0; i<K; ++i) {
        Casher c;
        c.idx = -i; c.rest = 0;
        cpq.push(c);
    }
 
    for(int i = 0; i<N; ++i) {
        Mem m;
        int stnum;
        cin >> m.mnum >> stnum;
        Casher c = cpq.top();
        cpq.pop();
        c.rest -= stnum;
        m.otime = c.rest;
        m.cidx = -c.idx;
        cpq.push(c);
        mpq.push(m);
    }
 
    long long ans = 0;
    int mul = 1;
    while(!mpq.empty()) {
        Mem m = mpq.top();
        mpq.pop();
        ans += (long long)m.mnum*(long long)mul++;
    }
    cout << ans;
}

 

 

 

 

 

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

17612번: 쇼핑몰

 

 

 

 

 

쇼핑몰

우선순위 큐 두개를 이용해 하나는 현재 이용할 수 있는 계산대를 구하기 위해 사용하고,

다른 하나는 고객들이 나가는 순서를 구하기 위해 사용하면 됩니다.