POJ 3750 小孩报数问题 解题报告

 

资源来源：http://blog.chinaunix.net/u3/105033/index.html

 

一、问题描述

Description

有N个小孩围成一圈，给他们从1开始依次编号，现指定从第W个开始报数，报到第S个时，该小孩出列，然后从下一个小孩开始报数，仍是报到S个出列，如此重复下去，直到所有的小孩都出列（总人数不足S个时将循环报数），求小孩出列的顺序。

Input

第一行输入小孩的人数N（N<=64）
接下来每行输入一个小孩的名字(人名不超过15个字符)
最后一行输入W,S (W < N)，用逗号","间隔

Output

按人名输出小孩按顺序出列的顺序，每行输出一个人名

Sample Input

5

Xiaoming

Xiaohua

Xiaowang

Zhangsan

Lisi

2,3

Sample Output

Zhangsan

Xiaohua

Xiaoming

Xiaowang

Lisi

 

二、分析解答

设置一个布尔数组b[]保存小孩子是否已经出列。通过mode=(S%count==0)?S:(S%count)计算出下一个小孩是第几个（从当前开始数），然后找到该小孩的编号，让其出列。以此循环，直到所有小孩出列。

 

三、代码

#include<iostream>
#include<string>
using namespace std;
int main()
{
    int N;
    int i;
    int W,S;
    cin>>N;
    string names[65];
    bool b[65];
    for(i=1;i<=N;++i)
    {
        cin>>names[i];
        b[i]=true;
    }
    char ch;
    cin>>W>>ch>>S;
    int flag=W;
    int count=N;
    for(i=1;i<=N;++i)
    {
        int mode;
        mode=(S%count==0)?S:(S%count);
        count--;
        int k=1;
        int j=flag;
        while(k<mode)
        {
            j=(j+1)>N?1:(j+1);
            while(b[j]==false)
            {
                j=(j+1)>N?1:(j+1);
            }
            k++;
        }
        b[j]=false;
        cout<<names[j]<<endl;
        if(i<N)
        {
            j=(j+1)>N?1:(j+1);
            while(b[j]==false)
            {
                j=(j+1)>N?1:(j+1);
            }
            flag=j;
        }
    }
    return 0;
}