티스토리 뷰

알고리즘 관련/BOJ

BOJ)1966 프린터 큐

JASON 자손9319 2017. 2. 21. 17:01

문제: icpc.me/1966


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


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


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


 

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
#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<intint>> 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;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)9577 토렌트  (0) 2017.02.22
BOJ)5430 AC  (0) 2017.02.21
BOJ)1966 프린터 큐  (0) 2017.02.21
BOJ)6064 카잉 달력  (0) 2017.02.21
BOJ)2787 흔한 수열 문제  (0) 2017.02.20
BOJ)2191 들쥐의 탈출  (0) 2017.02.20
TAG
,
댓글
댓글쓰기 폼