POJ1012 Joseph（约瑟夫环）

题目链接

题意：k 个好人 k 个坏人排成一行，求最小的 m（每次杀第 m 个人）使所有坏人先被杀死。

将所有人编号 0~2k-1，模拟每次杀人，杀人后将所有人重新排列（从第一个人编号为 0 开始），由于要先杀坏人，所以好人的编号应该是不变的。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<string>
using namespace std;

int main(){
    //freopen("a.txt", "r", stdin);
    int k;
    int joseph[14];  //记录答案
    memset(joseph, -1, sizeof(joseph));
    while(~scanf("%d", &k) && k){
        if(joseph[k] != -1) cout << joseph[k] << endl;
        else{
            int n = 2*k; //总人数
            int ans[35]; //第i轮杀死人的编号
            ans[0] = 0;
            int m = k;  //枚举m，编号k的人是第一个坏人
            for(int i = 1; i <= k; i++){ //i轮
                ans[i] = (ans[i-1]+m-1)%(n-i+1);  //模剩余的人数
                if(ans[i] < k){
                    i = 0;
                    m++;
                }
            }
            joseph[k] = m;
            cout << m << endl;
        }
    }
    return 0;
}