问题描述
p133原题链接:UVaOJ 133 - The Dole Queue
相关说明:本题为《算法竞赛入门经典(第2版)》例题 4-3
解法一:模拟
用数组来模拟循环链表,用 0 表示出局,1 表示还在,为了方便对上索引和编号,这里数组选择多开两个首尾元素 circle[0] 和 circle[n+1], 作为 pa 和 pb 的初始位置(并没有按照题目描述放在 1 和 n ),方便执行 count 函数的逻辑,这样它们第一步计数的时候就能分别跑到 0->1 和 n+1->n. 并通过取余来实现头尾位置的正确交换( circle[n]->circile[1] 或 circle[1]->circle[n] 取决于沿着环计数的方向),且要求每次移动都必须移动到下一个不为 0 的位置。紫书中将 pa 初始化为 n 其实也等于这里初始化为 circle[0] 的做法,都是为了使得第一次移动能到 1 这个位置,区别在于紫书是通过取余数的逻辑过来的。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
#include <bits/stdc++.h> using namespace std; int count(const vector<int> &c, int pos, int dir, int num) { int l = c.size() - 2; while (num--) do { pos = (pos - 1 + dir + l) % l + 1; } while (c[pos] != 1); return pos; } int main() { int n, k, m; while (cin >> n >> k >> m && n) { vector<int> circle(n + 2); for (int i = 1; i <= n; ++i) circle[i] = 1; int left = n, pa = 0, pb = n + 1; while (left) { pa = count(circle, pa, 1, k); pb = count(circle, pb, -1, m); cout << right << setw(3) << pa; left -= 1; if (pa != pb) { cout << right << setw(3) << pb; left -= 1; } circle[pa] = circle[pb] = 0; if (left) cout << ","; } cout << endl; } return 0; } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
from typing import List def count(c: List, pos: int, dir: int, num: int) -> int: l = len(c) - 2 for i in range(num): pos = (pos - 1 + dir + l) % l + 1 while (c[pos] != 1): pos = (pos - 1 + dir + l) % l + 1 return pos while True: n, k, m = map(int, input().split()) if not n: break circle = [0 for _ in range(n+2)] for i in range(1, n+1): circle[i] = 1 left, pa, pb = n, 0, n+1 while left: pa = count(circle, pa, 1, k) pb = count(circle, pb, -1, m) print(f"{pa:>3}", end="") left -= 1 if pa != pb: print(f"{pb:>3}", end="") left -=1 circle[pa] = circle[pb] = 0 print("," if left else "", end="") print("") |