133 The Dole Queue

题目描述

本题模拟了一个裁员队列的过程。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，数据规模很小，可以直接用数组模拟整个过程。

关键点分析

1. 模拟圆圈
   使用数组circle存储当前还在圈中的人的编号，被选中的人将其值置为000表示离开。

2. 数人逻辑

   • 逆时针方向（从当前位置right开始，数kkk个有效的人）
   • 顺时针方向（从当前位置left开始，数mmm个有效的人）
     由于选中的人会离开，所以数人时需要跳过值为000的位置。

3. 同时离开
   如果两个官员选中同一个人，只输出一次，并且只将nnn减少111；否则分别输出并减少222。

4. 输出格式
   使用setw(3)控制输出宽度为333字符，用逗号分隔不同对（或单独编号），注意末尾没有逗号。

算法步骤

1. 读入N,k,mN, k, mN,k,m，若全为000则结束。
2. 初始化数组circle为111到NNN。
3. 设置两个指针right和left，分别表示逆时针和顺时针的起始位置。
4. 当还有人未离开时：
   • 从right开始逆时针数kkk个有效位置，更新right为选中位置。
   • 从left开始顺时针数mmm个有效位置，更新left为选中位置。
   • 输出circle[right]（占333字符），将其置000，剩余人数减一。
   • 如果right != left，输出circle[left]（占333字符），将其置000，剩余人数再减一。
   • 如果还有人剩余，输出逗号。
5. 输出换行，处理下一组数据。

代码实现

// 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控制宽度和逗号的位置即可。