Algorithm/BOJ

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

jhg0406 2020. 8. 24. 13:08
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#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;
}
 cs

 

 

 

 

 

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

 

17612번: 쇼핑몰

입력의 첫 줄에는 2개의 정수 N(1 ≤ N ≤ 100,000)과 k(1 ≤ k ≤ 100,000)가 주어진다. 다음 줄부터 N개의 줄에 걸쳐 고객 N명의 정보가 줄 맨 앞의 고객부터 맨 뒤 고객까지 순서대로 주어진다. i번째 ��

www.acmicpc.net

 

 

 

 

 

쇼핑몰

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

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