UVA133(约瑟夫环变种)

地址：https://vjudge.net/problem/UVA-133

题目描述

为了缩短领救济品的队伍，NNGLRP决定了以下策略：每天所有来申请救济品的人会被放在一个大圆圈，面朝里面。选定一个人为编号 1 号，其他的就从那个人开始逆时针开始编号直到 N。一个官员一开始逆时针数，数 k 个申请者，然后另一个官员第 N 个始顺时针方向数 m 个申请者，这两个人就被送去再教育。如果两个官员数的是同一个人，那个人则被送去从政，然后2个官员再在剩下的人里面继续选直到没人剩下来，注意两个被选中的人是同时走掉的，所以就有可能两个官员选中一个人。

Input

输入含有多组测试资料，每组测试资料一列含有三个数 N，k 和 m（k, m > 0，0<N<20）。当输入为 0 0 0 代表输入结束。

Output

对每组测试资料输出一列。输出被选中的申请者的编号顺序（一对一对的）。每个数的宽度为 3 。每一对前面的那个编号为逆时针数的官员选出的，后面的那个编号为顺时针数的官员选出的（但是如果这2个官员选出同一个人，那就只会有一个编号）。每一对之间以逗号分开。格式请参考Sample Output。

Sample Input

Sample Output

 4 8, 9 5, 3 1, 2 6, 10, 7 
 4 11, 10 1, 8 6, 13 7, 3, 5 12, 9 2 
 1 3, 5 7, 2 4, 6



解析：
模拟，但坐标变换非常重要。
两套代码：

#include <bits/stdc++.h>
using namespace std;
int n,k,m;
int a[30];
int go(int p,int d,int t)
{
    while(t--)
    {
        do
        {
            p=(p+d+n-1)%n+1;//刘汝佳代码的巧妙之处
        }while(a[p]==0);
    }
    return p;
}
main()
{
    while(cin>>n>>k>>m&&n)
    {
         for(int i=1;i<=n;i++)
         a[i]=i;
         int left=n;int p1=n;
         int p2=1;
         while(left)
         {
             p1=go(p1,1,k);
             p2=go(p2,-1,m);
             printf("%3d",p1);
             left--;
             if(p2!=p1)
             {
                printf("%3d",p2);
                 left--;
             }
             a[p1]=a[p2]=0;
             if(left)
             cout<<",";
         }
         cout<<endl;
    }
}

更易于理解的代码:

#include<iostream>
#include<cmath>
#include<vector>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int maxn=30;
int vis[maxn];
int n,k,m;
int main()
{
    while(scanf("%d%d%d",&n,&k,&m)==3&&n)
    {
    //    vector<int>vis(n);
        memset(vis,0,sizeof(vis));
        int ki=0,mi=n-1,cnt=0,cntk=0,cntm=0;
        while(cnt<n)
        {
            while(1)
            {
                if(vis[ki]!=-1)
                    cntk++;
                if(cntk==k)
                    break;
                ki=(ki+1)%n;
            }
            while(1)
            {
                if(vis[mi]!=-1)
                    cntm++;
                if(cntm==m)
                    break;
                mi=(mi+(n-1))%n;　　//顺时针，+代替-
            }
            if(ki==mi)
            {
                vis[ki]=-1;
                cnt++;
                printf("%3d%s",ki+1,cnt==n?"":",");
            }
            else
            {
                vis[ki]=-1;
                vis[mi]=-1;
                cnt+=2;
                printf("%3d%3d%s",ki+1,mi+1,cnt==n?"":",");
            }
            cntk=0,cntm=0;
        }
        cout<<endl;
    }
}