洛谷 P1145 约瑟夫

题目描述

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

感谢yh大神指出样例数据的错误。

输入输出格式

输入格式：

一个k，0<k<14

输出格式：

一个m

输入输出样例

输入样例#1：

3

输出样例#1：

5

输入样例#2：

4

输出样例#2：

30

说明

0<k<14

屠龙宝刀点击就送

70分环形队列

#include <cstdio>
int k,next[30];
bool check(int m)
{
    int pos=2,gs=0,j=1,sum=0;
    for(;gs<k*2;)
    {
        for(;pos<m;pos++) j=next[j];
        if(next[j]>k) sum++;
        if(next[j]<=k&&sum<k) return false;
        if(next[j]<=k&&sum==k) return true;
        pos=1;gs++;next[j]=next[next[j]]; 
    }
}
int main()
{
    scanf("%d",&k);
    for(int i=1;i<k*2;++i) next[i]=i+1;
    next[k*2]=1;
    for(int i=k+1;;++i)
    {
        if(check(i))
        {
            printf("%d",i);
            return 0;
        }
        for(int i=1;i<k*2;++i) next[i]=i+1;next[k*2]=1;
    }
    return 0;
}

AC代码 

#include <cstdio>
int flag,ans,now,k;
bool check(int Remain)
{
    int nextt=(now+ans-1)%Remain;
    if(nextt>=k) {now=nextt;return 1;} 
    else return 0;
}
int main()
{
    scanf("%d",&k);
    for(ans=k+1;!flag;++ans)
    {
        now=0;flag=1;
        for(int i=0;i<k;++i)
         if(!check(2*k-i)) {flag=0;break;}
    }
    printf("%d
",ans-1);
    return 0;
}