[BOJ] 쇼핑몰 - Compy's Blog

쇼핑몰

TimeLimit	MemoryLimit	Condition	TAG
1s	512MB	(1 ≤ N ≤ 100,000 1 ≤ k ≤ 100,000 1 ≤ id_i ≤ 1,000,000 1 ≤ w_i ≤ 20)	Greedy

문제는 전형적인 priority_queue.. 즉 우선순위 큐를 활용한 풀이가 가능하다라는 것을 엄청 강하게 풍기고 있다..

나는 그걸 알고 바로 들어갔는데 코드가 와… 이상한 곳에 빠져서 엄청 고민했다.

실시간 업데이트를 시키면서 진행하는데.. 이때 같은 시간에 있는 소비자들을 전부 처리하고 다음에 들어오는 사람들을 받은게 아니라 한명 나가면 바로 업데이트 하고 들어오게 하면서 순서가 꼬이게 되었다. 또 마지막에 K의 길이가 1인 case에 대해서도 한번 틀리고서야 반례 찾고 고쳤는데… 아 정말 이런 디테일에 있어서 아직 나는 많이 부족한 것 같다.

지금 골드를 최대한 1시간 이내로 푸는 목표인데… 수학, dp 같은 경우는 2시간 정도 안에는 무조건 푸는걸로 하고 있는데… 이문제는 무려 1시간 10분 정도 잡고 있었다.

으아ㅏㅏㅏ 아직도 갈 길이 멀다.. 계속해서 성장해 나가자..

정답 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
using namespace std;
using ll = long long;

struct consumer {
    ll cost, id, k;
    
    
};
struct CompareConsumer {
    bool operator()(const consumer& a, const consumer& b) {
        if(a.cost == b.cost) return a.k < b.k;
        return a.cost > b.cost;
    }
};

pair<ll, ll> consumers[100'000];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    priority_queue<consumer, vector<consumer>, CompareConsumer> q;
    priority_queue<ll, vector<ll>, greater<ll>> ks;
    ll n, m;
    cin >> n >> m;
    
    ll a_, b_;
    for(int i = 0; i < n; i++){
        if(i < m) ks.push(i);
        cin >> a_ >> b_;
        consumers[i] = {a_, b_}; // id, cost
    }

    
    ll current = 0;
    ll idx = 0;
    
    ll result = 0;
    ll result_idx = 1LL;
    
    do{
        if(q.size() < m && idx < n) {
            ll k = ks.top(); ks.pop();
            auto [a, b] = consumers[idx++];
            q.push({current + b, a, k});
//            cout << "in: " << current + b << " " << a << " " << k << "\n";
            continue;
        }
        ll back = -1;
        do{
            auto [a, b, k] = q.top(); q.pop();
            ks.push(k);
//            cout << "out: " << a << " " << b << " " << k << "\n";
            if(a != current) current = a;
//            cout << b*result_idx << "\n";
            result+= b*result_idx++;
            back = a;
        }while(!q.empty() && back == q.top().cost);
//        cout << result << "\n";
    }while(!q.empty() || idx < n);
    
    
    cout << result;
    return 0;
}

/*
 5 1
 1 1
 2 1
 3 1
 4 1
 5 1
 */