【UVA-133】The Dole Queue【紫书】

【UVA-133】The Dole Queue【紫书】

问题链接:https://vjudge.net/problem/UVA-133

Solution:

这道题的关键就是充分利用取余运算。由于对n取余会导致结果不存在n这个数,而多出0这个数,我们将0单独映射为n就好,这样做是可行的,因为围成一个圈0与n相对于其它数的位置是相同的。

需要注意的一点是,由于题设要求已经去除的人不会再参加到这个圈里,所以我们使用set判重,但是仅仅这样是不够的,我们需要注意对于取下个位置的时候不能够直接加上间隔,而应该依次加1个间隔,如果这个人的编号已经放到了set中,应当顺次取下一个位置,直到取到没有出现过的编号,对于逆时针转的人执行k次上述过程,顺时针转的人执行m次上述过程,确保确实遍历够指定人数【如果直接+k或-m再取余可能会出现一种情况:确实找到了一个没有出现过的人,但是与上一个出现的人的实际间隔可能不足k或m,因为中间有人已经离队了】。

#include <iostream>
#include <set>

using namespace std;

int main(void) {
    int n, k, m, kpos, mpos;
    set<int> s;
    while (~scanf("%d%d%d", &n, &k, &m) && (n || k || m)) {
        kpos = 0;
        mpos = 1;
        s.clear();
        for (int t = 0; s.size() < n; t++) {
            if (t) putchar(',');
            for (int i = 0; i < k; i++)
                do { kpos = (kpos + 1) % n; } while (s.find(kpos) != s.end());
            for (int i = 0; i < m; i++)
                do { mpos = (mpos - 1 + n) % n; } while (s.find(mpos) != s.end());
            s.insert(kpos), s.insert(mpos);
            if (kpos == mpos) printf("%3d", kpos ? kpos : n);
            else printf("%3d%3d", kpos ? kpos : n, mpos ? mpos : n);
        }
        putchar('\n');
    }
    return 0;
}