티스토리 뷰

알고리즘 관련/BOJ

BOJ)1168 조세퍼스 문제2

JASON 자손9319 2017. 1. 11. 01:07

문제: icpc.me/1168


N명의 사람이 원을 이루며 앉아있고 M번째 사람을 제거하면서 진행할 때 제거되는 순서에 따른 순열을 출력하는 문제이다.


세그먼트 트리를 이용하여 현재 위치에서 M번째 사람을 찾아내서 풀면 된다. 이때 주의 할 점은 환형이기 때문에 남아있는 사람수를 고려하여 모듈러 연산이 필요하다.  


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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int seg[400040];
int n, m;
vector<int> ans;
int update(int pos, int val, int node, int x, int y) {
    if (pos < x || y < pos)
        return seg[node];
    if (x == y)
        return seg[node] = val;
    int mid = (x + y) >> 1;
    return seg[node] = update(pos, val, node * 2, x, mid) + update(pos, val, node * + 1, mid + 1, y);
}
int query(int val, int node, int x, int y) {
    if (x == y)
        return x;
    if (seg[node * 2>= val)
        return query(val, node * 2, x, (x + y) / 2);
    else
        return query(val - seg[node * 2], node * + 1, (x + y) / + 1, y);
}
int squery(int lo, int hi, int node, int x, int y) {
    if (y < lo || hi < x)
        return 0;
    if (lo <= x&&<= hi)
        return seg[node];
    int mid = (x + y) >> 1;
    return squery(lo, hi, node * 2, x, mid) + squery(lo, hi, node * + 1, mid + 1, y);
}
int main()
{
    scanf("%d%d"&n, &m);
    for (int i = 1; i <= n; i++)
        update(i, 111, n);
    int mod = n - 1;
    ans.push_back(m);
    update(m, 011, n);
    for (int i = 2; i <= n; i++) {
        int x = (squery(1, ans.back(), 11, n) + m) % mod;
        if (!x)x = mod;
        ans.push_back(query(x, 11, n));
        update(ans.back(), 011, n);
        mod--;
    }
    printf("<");
    for (int i = 0; i < ans.size(); i++) {
        if (i == ans.size() - 1)
            printf("%d>\n", ans[i]);
        else
            printf("%d, ", ans[i]);
    }
    return 0;
}
cs


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

BOJ)5012 불만 정렬  (2) 2017.01.11
BOJ)3002 아날로그 다이얼  (0) 2017.01.11
BOJ)1168 조세퍼스 문제2  (0) 2017.01.11
BOJ)9426 중앙값 측정  (7) 2017.01.11
BOJ)5676 음주 코딩  (0) 2017.01.10
BOJ)12016 라운드 로빈 스케줄러  (0) 2017.01.10
댓글
댓글쓰기 폼