洛谷P1145约瑟夫_p1145 约瑟夫

题目描述

n 个人站成一圈，从某个人开始数数，每次数到 m 的人就被杀掉，然后下一个人重新开始数，直到最后只剩一个人。现在有一圈人，k 个好人站在一起，k 个坏人站在一起。从第一个好人开始数数。你要确定一个最小的 m，使得在第一个好人被杀死前，k 个坏人先被杀死。

输入格式

一行一个整数 k。

输出格式

一行一个整数 m。

输入输出样例

输入 #1

3

输出 #1

5

输入 #2

4

输出 #2

30

#include<bits/stdc++.h>
using namespace std;
int k,x,m;
 
int main()
{
    cin>>k;
    m=k+1;//初值
    while(1)
    {
        bool flag=0;
        x=0;
        for(int i=0;i<k;i++)
        {
            x=(x+m-1)%(2*k-i);//右边是上一次删除的位置，左边是更新后删除的位置
            if(x<k)//好人被删除
            {
                flag=1;
                break;
            }
        }
        if(flag==0)//一个好人都没淘汰
        {
           cout<<m<<endl;
           return 0;
        }
        m++;
    }
 
    return 0;
}