UVA 133 The Dole Queue(报数问题)

题意：一个长度为N的循环队列，一个人从1号开始逆时针开始数数，第K个出列，一个人从第N个人开始顺时针数数，第M个出列，选到的两个人要同时出列（以不影响另一个人数数），选到同一个人就那个人出列。

思路：用数组来操作，详情见代码吧。

#include <iostream>
#include <stdio.h>
#include <string>

/*
用数组存储序号，从左到右依次为1~n。
逆时针相当于从左往右依次数，大于n再从1开始，用right作为指针。
顺时针相当于从右往左依次数，小于1再从n开始，用left作为指针。
*/
using namespace std;
const int maxn=25;
int p[maxn]; //存储一开始的序列
int n,k,m;

int main()
{
    while(scanf("%d%d%d",&n,&k,&m)!=EOF){
        if(n==0&&k==0&&m==0)
            break;
        int first=1;
        for(int i=0;i<=n;i++)
            p[i]=i+1;
        int left=n-1,right=0;
        do{
            //n为剩余人的个数，下面是计算此次被数到的人的位置
            right=(right+n+k-1)%n;
            //从left开始往左数m个，相当于从left开始往右数n-(m-1)个
            left=((left+n-(m-1))%n+n)%n;  //注意这里很有可能会出现负数，所以加n再模一次
            if(left==right){
                if(first)
                    printf("%3d",p[left]);
                else
                    printf(",%3d",p[left]);
                first=0;
                for(int i=left;i<n;i++)
                    p[i]=p[i+1];
                //因为left是往左移的，后面的数往左移动，指针也要往左移动，使left指向出列的那个人的前一个人
                //而由于right是往右数的，后面的数往左移动，right自动指向后一个(即出列的那个人的后一个)，所以不需要变动
                left--;
                if(left<0 && n>1)
                    left=(left+n-1)%(n-1);
                n--;
            }
            else{
                if(first)
                    printf("%3d%3d",p[right],p[left]);
                else
                    printf(",%3d%3d",p[right],p[left]);
                first=0;
                //left指针在right之前
                if(left<right){
                    for(int i=right;i<n;i++)
                        p[i]=p[i+1];
                    for(int i=left;i<n-1;i++)
                        p[i]=p[i+1];
                    /*
                      right后面的数都往左移动1次
                      left后面的数都往左移动2次，
                      由于right指针是往右移动的，所以为了指向出列的人的后一个，right要减1
                      left指针则是往左移动的，这里要往左移动1格，指向出列的人的前一个。
                    */
                    right--;
                    if(right<0 && n>2)
                    right=(right+n-2)%(n-2);
                    left--;
                    if(left<0 && n>2)
                    left=(left+n-2)%(n-2);
                }
                //left指针在right之后
                else{
                    for(int i=left;i<n;i++)
                        p[i]=p[i+1];
                    for(int i=right;i<n-1;i++)
                        p[i]=p[i+1];
                    /*left指针后面的数都往左移动1次
                      right指针后面的数都往左移动2次，
                      由于right指针是往右移动的，当后面的数往左移动，right自动指向出列的人的后一个，所以不需要变动。
                      left指针则是往左移动的，这里要往左移动2格，指向出列的人的前一个。
                    */
                    left-=2;
                    if(left<0 && n>2)
                    left=(left+n-2)%(n-2);
                }
                n-=2;
            }
        }while(n);
        printf("
");
    }
    return 0;
}