KOI 2019 1차 고등부 1번 쇼핑몰

문제 링크 : https://www.acmicpc.net/problem/17612

문제 풀이

딱히 사고의 흐름이라고 할 게 없다. 상황의 형태와 여러가지 조건들을 주어지고 이를 시뮬레이팅 할 수 있는 코드를 짜는 구현 문제이기 때문이다. 

고객들이 어떤 순서로 나갈지를 알아내야 한다. 고객들은 번호 순으로 입장하고, 빈 구역이 있으면 바로 입장하며, 각 고객별로 주어진 시간만큼 있다가 퇴장한다. 이때 입장할 구역이 여러군데면 가장 작은 번호로 가며, 나갈 때는 동시에 끝나면 번호가 큰 순서대로 나간다.

정리하면 나가는 순서는 일련의 규칙을 따른다. 일련의 규칙에 따른 정렬 -> 우선순위 큐. 솔직히 따지고 보면 우선순위 큐 연습문제라고 봐도 무방하다. 

동시에 자리가 나면 무조건 작은 번호의 구역으로 이동하기 때문에 빈 구역을 표시할 우선순위 큐 하나와 진행상황 우선순위 큐를 준비한다. 진행상황 우선순위 큐는 시간, 위치를 저장하고 있어서 시간이 작고 위치가 큰 순서대로 pq를 가지고 있으면 된다.

pq에서 가장 위에 있는 원소를 뽑으면서 이와 끝나는 시간이 같은 모든 원소를 차례대로 뽑는다. 그 뽑은 원소에 해당하는 위치를 다시 빈 구역 pq에 넣어준다. 이를 반복하면서 어떤 사람에 대한 원소 순서대로 뽑히는지 기록을 해 놓고 나중에 계산을 하면 문제를 해결할 수 있다. 자세한 것은 코드를 보는 것이 훨씬 도움이 될 것 같다. 

코드

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pii;
typedef pair<ll,pii> piii; // 시간 위치 사람
#define ff first
#define ss second 
 
priority_queue<piii,vector<piii>,greater<piii>> pq;
priority_queue<ll,vector<ll>,greater<ll>> emp;
ll arr[1010101]; //번호
ll arr2[1010101]; //물건 수 
ll chk[1010101];
 
int main(){
    ll i,j,k,l,m,n;
    scanf("%lld %lld",&n,&m);
 
    for(i=1;i<=n;i++)
        scanf("%lld %lld",&arr[i],&arr2[i]);
    for(i=1;i<=m;i++)
        emp.push(i);
    ll cnt=0;
    ll t=0;
    ll ans=0;
    ll fin=0;
    for(i=1;i<=n+m;i++){
        while(emp.size()&&cnt!=n){
            ll k=emp.top();
            emp.pop();
            cnt++;
            pq.push({t+arr2[cnt],{-k,arr[cnt]}});
        }
        if(fin==n) break;
        if(!pq.empty()){
            t=pq.top().ff;
            while(pq.size()&&pq.top().ff==t){
                auto k=pq.top();
                pq.pop();
                emp.push(-k.ss.ff);
                fin++;
                ans+=fin*k.ss.ss;
            }
        }
    }
    printf("%lld",ans);
}