Skip to content

14149: 【原4149】Josephus

题目

题目描述

author: DS TA 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4149

Description

假设n个人坐成一圈,按顺时针顺序由1开始给他们编号,然后由第一个人从1开始顺时针报数,数到m的人出局,下一个人从1开始重新报数。

现在要求的是第k个出局的人的编号。

Input Format

输入包括三个整数,即n,m,k,之间用空格分开,保证n,m,k关系合法。

Output Format

输出一个整数,代表第k个出局的人的编号。

Sample Input1

4 2 1

Sample Output1

2

Sample Input2

4 2 2

Sample Output2

4

BugenZhao's solution

//
// Created by BugenZhao on 2019/4/10.
//

#include <iostream>

using namespace std;

using ll=long long;

int main() {
    ll n, m, k;
    cin >> n >> m >> k;
    auto out = new bool[n]{};
    ll cur = -1;
    while (k--) {
        ll mm = m;
        while (mm) {
            cur = (cur + 1) % n;
            while (out[cur]) {
                cur = (cur + 1) % n;
            }
            --mm;
        }
        out[cur] = true;
    }
    cout << cur + 1 << endl;
    return 0;
}

ligongzzz's solution

#include "iostream"
#include "cstdio"
using namespace std;

constexpr int max_num = 20000000;

bool remain[max_num] = { 0 };

int main() {
    long long n, m, k;
    cin >> n >> m >> k;

    long long cnt = n, cur_pos = 0;
    for (; k > 0; --k) {
        long long dis = m % cnt;
        if (dis == 0)
            dis = cnt;
        for (long long i = 0; i < dis;) {
            ++cur_pos;
            if (cur_pos > n)
                cur_pos = 1;
            if (!remain[cur_pos]) {
                ++i;
            }
        }
        remain[cur_pos] = true;
    }

    cout << cur_pos;

    return 0;
}

skyzh's solution

#include <iostream>
using namespace std;

struct Node {
    int x;
    Node* next;
    Node(int x, Node* next = NULL) : x(x), next(next) {}
};

int main() {
    int n, m, k;
    Node* head = new Node(0);
    Node* ptr = head;
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
        Node* cur = new Node(i);
        ptr->next = cur;
        ptr = cur;
    }
    ptr->next = head->next;
    ptr = head->next;
    Node* prev = head;
    int cnt_m = 0;
    while (true) {
        ++cnt_m;
        if (cnt_m == m) {
            prev->next = ptr->next;
            --k;
            if (k == 0) {
                cout << ptr->x << endl;
                return 0;
            }
            cnt_m = 0;
            delete ptr;
        }
        prev = prev->next;
        ptr = ptr->next;
    }
    return 0;
}