【华为练习题】约瑟夫问题拓展

【华为练习题】约瑟夫问题拓展

题目

功能: 约瑟夫问题众所周知，原始的约瑟夫问题是这样的：有n个人，编号为1,2,…, n，站成一圈，
每次第m个将会被处决，直到只剩下一个人。约瑟夫通过给出m来决定赦免其中的一个人。
例如当n=6,m=5时，5,4,6,2,3将会被依次处决，而1将会幸免。

假如有k个好人，和k个坏人，所有人站成一圈，前k个人是好人，后k个人是坏人，
编写程序计算一个最小的m，使k个坏人都被处决，而不处决任何好人。

输入: k 为正整数
输出:
返回: 最小的m，使k个坏人都被处决，而不处决任何好人。

解答

#include <vector>
using namespace std;

bool isRight(int k, int m){
    vector<int> v;
    for (int i = 0; i < 2 * k; i++)
    {
        v.push_back(i+1);
    }
    int start = 0;
    for (int i = 0; i < k; i++)
    {
        int index = (start + m - 1) % v.size();
        if (v[index] <= k)
        {
            return false;
        }
        v.erase(v.begin() + index);
        start = index % v.size();
    }
    return true;
}

int cycle(int k){
    int m = k;
    while (!isRight(k,++m));
    return m;
}

int main()
{
    int k;
    cin >> k;
    cout << cycle(k) << endl;
    return 0;
}