题目描述
本题模拟了一个裁员队列的过程。NNN个申请人围成一个圆圈，从编号111开始逆时针编号到NNN。每天，两位官员分别从编号111（逆时针方向）和编号NNN（顺时针方向）开始数人。一位官员每次数kkk个有效申请人（跳过已被选中的人），另一位官员每次数mmm个有效申请人。被选中的两个人将同时离开圆圈（如果两人选中同一人，则该人仅离开一次）。重复此过程，直到所有人都被选中。要求按离开的顺序输出编号，每对编号（或单独编号）占333字符宽，用逗号分隔，末尾不加逗号。
输入格式
多组数据，每组一行三个整数N,k,mN, k, mN,k,m，满足k,m>0,0<N<20k, m > 0, 0 < N < 20k,m>0,0<N<20。以0 0 0结束输入。
输出格式
对每组数据，输出一行，表示离开顺序，格式如上所述。
样例输入
10 4 3 0 0 0样例输出
4 8, 9 5, 3 1, 2 6, 10, 7解题思路
本题是一个典型的约瑟夫环问题的变种，区别在于有两个方向同时进行数人，且每次选中的两人同时离开。由于N<20N < 20N<20，数据规模很小，可以直接用数组模拟整个过程。
关键点分析
模拟圆圈
使用数组circle存储当前还在圈中的人的编号，被选中的人将其值置为000表示离开。数人逻辑
- 逆时针方向（从当前位置
right开始，数kkk个有效的人） - 顺时针方向（从当前位置
left开始，数mmm个有效的人）
由于选中的人会离开，所以数人时需要跳过值为000的位置。
- 逆时针方向（从当前位置
同时离开
如果两个官员选中同一个人，只输出一次，并且只将nnn减少111；否则分别输出并减少222。输出格式
使用setw(3)控制输出宽度为333字符，用逗号分隔不同对（或单独编号），注意末尾没有逗号。
算法步骤
- 读入N,k,mN, k, mN,k,m，若全为000则结束。
- 初始化数组
circle为111到NNN。 - 设置两个指针
right和left，分别表示逆时针和顺时针的起始位置。 - 当还有人未离开时：
- 从
right开始逆时针数kkk个有效位置，更新right为选中位置。 - 从
left开始顺时针数mmm个有效位置，更新left为选中位置。 - 输出
circle[right]（占333字符），将其置000，剩余人数减一。 - 如果
right != left，输出circle[left]（占333字符），将其置000，剩余人数再减一。 - 如果还有人剩余，输出逗号。
- 从
- 输出换行，处理下一组数据。
代码实现
// The Dole Queue// UVa ID: 133// Verdict: Accepted// Submission Date: 2015-12-13// UVa Run Time: 0.000s//// 版权所有（C）2015，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intn,k,m;vector<int>circle;// count off in counter-clockwise and return the index of target.intfindCCW(intright,intnumber){for(inti=right;i<circle.size();i++)if(circle[i]>0&&((--number)==0))returni;while(true){for(inti=0;i<circle.size();i++)if(circle[i]>0&&((--number)==0))returni;}}// count off in clockwise and return the index of target.intfindCW(intleft,intnumber){for(inti=left;i>=0;i--)if(circle[i]>0&&((--number)==0))returni;while(true){for(inti=circle.size()-1;i>=0;i--)if(circle[i]>0&&((--number)==0))returni;}}intmain(){setfill(' ');while(cin>>n>>k>>m,n||k||m){circle.clear();for(inti=1;i<=n;i++)circle.push_back(i);intright=0,left=n-1;while(n>0){right=findCCW(right,k);left=findCW(left,m);cout<<setw(3)<<circle[right];circle[right]=0;n--;if(right!=left){cout<<setw(3)<<circle[left];circle[left]=0;n--;}if(n>0)cout<<",";}cout<<endl;}return0;}复杂度分析
- 时间复杂度：每次数人最多遍历整个数组，总复杂度为O(N2)O(N^2)O(N2)，由于N≤20N \leq 20N≤20，完全可行。
- 空间复杂度：O(N)O(N)O(N)。
总结
本题是一个有趣的模拟题，关键在于理解两个方向同时数人的逻辑，并处理好选中同一人的特殊情况。输出格式要求较严格，注意使用setw控制宽度和逗号的位置即可。
