정올 3337 / 백준 17612 쇼핑몰

algorithm : priority_queue

 

해설

이문제에서는 2가지의 priority_queue를 사용해야한다

1번째  기달려야 할시간이 같을 경우 가장 작은 번호가 계산대로 안내한다

2번째 계산시간이 같을 경우 높은 계산대 번호가 먼저 나간다

 

이 2가지 경우를 정의 하여 풀면된다

 

#include<bits/stdc++.h>
#define LM 100000+10
using ll = long long;
using namespace std;
  
int N,K;
struct data{
    int id, num, tm;
    bool operator<(const data&r)const{
        if(tm!=r.tm)return tm > r.tm;
        return num > r.num;
    }
}A[LM];
priority_queue<data> pq;
  
ll ans;
vector<data>res;
  
bool comp(const data&l, const data&r){
    if(l.tm != r.tm)return l.tm < r.tm;
    return l.num > r.num;
}
  
void input(){
    scanf("%d %d",&N,&K);
    int id,tm;
    for(int i=1;i<=N;i++){
        scanf("%d %d",&id,&tm);
        A[i] = {id,0,tm};
    }
}
  
void cart(){
    int i;
    data t;
    for(i=1;i<=N&&i<=K;i++)
        pq.push({A[i].id, i, A[i].tm});
    for(;i<=N;i++){
        t = pq.top();
        pq.pop();
        res.push_back(t);
        pq.push({A[i].id, t.num, t.tm + A[i].tm});
    }
    while(!pq.empty()){
        t = pq.top();
        pq.pop();
        res.push_back(t);
    }
    sort(res.begin(),res.end(),comp);
    for(i = 0;i < res.size(); i++)
        ans += (ll)res[i].id *(i + 1);
    printf("%lld",ans);
}
  
int main(){
    //freopen("input.txt","r",stdin);
    input();
    cart();
    return 0;
}