BOJ)1966 프린터 큐

문제: icpc.me/1966

큐에서 priority가 가장 높지 않으면 뽑은 뒤 맨 뒤로 보낼 때 m번째 수는 몇번째로 뽑히는지 출력하는 문제이다.

N이 100밖에 되지 않으므로 N^2 시뮬레이션을 돌려주면 된다.

들어오는 모든 수를 priority queue 와 queue에 넣어준 후 pq의 top과 queue의 front값이 같을 때만 값을 뽑아주면 된다.

 

#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
int t, n, m, x, r;
int main() {
    scanf("%d", &t);
    while (t--) {
        r = 0;
        queue<pair<int, int>> qu;
        priority_queue<int> pq;
        scanf("%d%d", &n, &m);
        for (int i = 0; i < n; i++) {
            scanf("%d", &x);
            qu.push({ x,i });
            pq.push(x);
        }
        while (qu.size()) {
            int here = qu.front().first;
            int num = qu.front().second;
            qu.pop();
            if (pq.top() == here) {
                r++;
                pq.pop();
                if (num == m)break;
            }
            else qu.push({ here,num });
        }
        printf("%d\n", r);
    }
    return 0;
}