救济金发放( The Dole Queue, UVa 133)

题目描述:

n(n<20)个人站成一圈,逆时针编号为 1~n。有两个官员,A从1开始逆时针数,B从n开始顺时针数。在每一轮中,官员A数k个就停下来,官员B数m个就停下来(两个官员有可能能停在同一个人上)。接下来被官员选中的1个或2个人离开队伍。

输入格式 输入n ,k ,m ,可能有多组数据,以 0 0 0结尾。

输出格式 输出每轮里被选中的人的编号(如果有两个人,先输出被A选中的)。输出的每个数应正好占3列。样例中的“ ␣ ”代表一个空格。

输入样例:

10 4 3
0 0 0

输出样例:

␣␣4␣␣8,␣␣9␣␣5,␣␣3␣␣1,␣␣2␣␣6,␣10,␣␣7

思路:一圈n个人可以看成一个循环队列,设置n个标志位来表示某个人有没有被选中并离开队伍,只有标志位为false的元素才是循环队列的有效元素。设置两个游标表示官员A和B当前所指向的元素,每次输出就是将A的游标向后循环移动k位,B的游标向前循环移动m位(移动过程中跳过无效元素)并输出,将输出元素的标志位设置为false,直至循环队列中所有元素标志均为false。

个人代码:

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n, k, m, A, B;
    while(cin >> n >> k >> m && n)
    {
        //当前所数到的元素下标
        A = -1, B = n;
        //当前所属到的元素个数
        int cntA = 0, cntB = 0;
        vector<bool>flagArr(n, false);
        vector<bool>flagTrue(n, true);
        bool flagSta = true;
        while(flagArr != flagTrue)
        {
            if (!flagSta)
                cout << ",";
            flagSta = false;
            //A数到下k个
            while (cntA < k)
            {
                do
                {
                    A = (A + 1) % n;
                }while(flagArr[A]);
                ++cntA;
            }
            //B数到下m个
            while (cntB < m)
            {
                do
                {
                    B = (n + B - 1) % n;
                }while(flagArr[B]);
                ++cntB;
            }
            cntA = cntB = 0;
            flagArr[A] = flagArr[B] = true;
            if (A == B)
                printf("%3d", A + 1);
            else
                printf("%3d%3d", A + 1, B + 1);
        }
        printf("\n");
    }
    return 0;
}

参考代码:

#include<stdio.h>
#define maxn 25
int n, k, m, a[maxn];

// 逆时针走t步,步长是d(-1表示顺时针走),返回新位置
int go(int p, int d, int t) {
  while(t--) {
    do { p = (p+d+n-1) % n + 1; } while(a[p] == 0); // 走到下一个非0数字
  }
  return p;
}

int main() {
  while(scanf("%d%d%d", &n, &k, &m) == 3 && n) {
    for(int i = 1; i <= n; i++) a[i] = i;
    int left = n; // 还剩下的人数
    int p1 = n, p2 = 1;
    while(left) {
      p1 = go(p1, 1, k);
      p2 = go(p2, -1, m);
      printf("%3d", p1); left--;
      if(p2 != p1) { printf("%3d", p2); left--; }
      a[p1] = a[p2] = 0;
      if(left) printf(",");
    }
    printf("\n");
  }  
  return 0;
}

 

上一篇:java内存模型(JSR-133内存模型)


下一篇:LeetCode-133克隆图(图的遍历+深拷贝概念)