UVA 113 - The Dole Queue
程序员文章站
2022-06-02 21:24:52
...
题目大意:
两位官员发放救济金,接受救济金的人排成一个圈,按照逆时针顺序从1-n编号。A官员每天从逆时针开始,数到第k个人,B官员从顺时针开始,数到第m个人,被数到的人出队接受救济金(可能数到同一个人),然后继续这个循环,直到所有人都被发到救济金为止。多组输入,n是人数,k是A官员每次数的人,m是B官员每次数的人,n/k/m为0时结束。输出每天接受救济金的人的编号,每个编号占3个空格位,每组之间用逗号分开。
代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#define maxn 100
using namespace std;
int main()
{
int n,k,m;
int a[maxn];
while(cin >> n >> k >> m && n != 0)
{
for(int i=0; i<n; i++)
{
a[i] = i+1; //初始化编号
}
int cnt1=0,cnt2=0; //逆时针和顺时针计数
int leave=0; //出队人数
int p1=0,p2=0; //出队人的编号
int i=0,j=n-1; //初始指针,分别指队首和队尾
int find1 = 0,find2 = 0; //标记是否找到
while(leave != n)
{
while(!find1)
{
if(i>=n) i=i%n;
if(a[i] != 0)
cnt1++;
if(k == cnt1)
{
find1 = 1;
p1 = a[i];
leave++;
cnt1 = 0;
}
else
i++;
}
printf("%3d",p1);
find1 = 0;
while(!find2)
{
if(j<0) j=n-1;
if(a[j] != 0)
cnt2++;
if(m == cnt2)
{
find2 = 1;
p2 = a[j];
cnt2 = 0;
if(p2 != p1)
{
a[j] = 0;
leave++;
}
}
else
j--;
}
find2 = 0;
a[i] = 0;
if(p2 != p1)
printf("%3d",p2);
if(leave != n)
printf(",");
}
printf("\n");
}
return 0;
}
反思:
约瑟夫问题的进阶版,双端选人,求出队序列。可以选择链表模拟或者数组模拟,因为是双端操作,且n<20,所以这里可以用数组模拟。出队的人置为0就可以,遍历时遇到0就跳过。A和B各一个循环,选出两个或一个人后再把对应的数组置0。