티스토리 뷰

알고리즘 관련/BOJ

BOJ)14195 DotB

JASON 자손9319 2017. 11. 15. 02:33

문제: icpc.me/14195

각 테스트 케이스마다 n과 c가 주어진다. 이후 n개의 시퀀스가 주어진다.

이제 0번 인덱스부터 증가하는 순서로 보면서 시퀀스를 c만큼 감소시킬 것이다. 해당 원소가 0이하가 되면 시퀀스의 탐색 방향을 반대방향으로 바꾸고 해당 원소를 제거한다.

이렇게 하였을 때, n+5번 탐색을 하였을 때 가장 마지막에 감소 된 원소의 번호를 출력하는 문제이다.

n이 적은편이기 때문에 시뮬레이션을 돌려주면 된다.

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
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int t, r, n, c;
int func(vector<pair<intint>> vt, int idx, int dir, int cnt) {
    if (vt.size() == 1)
        return vt[0].first;
    if (cnt == 1)
        return vt[idx].first;
    vt[idx].second -= c;
    if (vt[idx].second <= 0) {
        vt.erase(vt.begin() + idx);
        if (dir) {
            dir = 0;
            if (idx == vt.size())
                idx = 0;
        }
        else {
            idx--;
            dir = 1;
            if (idx == -1)
                idx = vt.size() - 1;
        }
    }
    if (dir)
        return func(vt, (idx + 1) % vt.size(), dir, cnt - 1);
    else
        return func(vt, (idx - + vt.size()) % vt.size(), dir, cnt - 1);
}
int main() {
    scanf("%d"&t);
    while (t--) {
        scanf("%d%d"&n, &c);
        vector<pair<intint>> vt;
        for (int i = 1; i <= n; i++) {
            int x;
            scanf("%d"&x);
            vt.push_back({ i,x });
        }
        printf("%d\n", func(vt, 01, n + 5));
    }
    return 0;
}
cs


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

BOJ)11670 초등 수학  (0) 2017.11.15
BOJ)3136 평면도  (0) 2017.11.15
BOJ)14195 DotB  (0) 2017.11.15
BOJ)14748 Flow Graph Complexity  (0) 2017.10.24
BOJ)5846 Tractor  (0) 2017.10.24
BOJ)5849 Cow Crossings  (0) 2017.10.24
TAG
댓글
댓글쓰기 폼