UVaOJ 133 - The Dole Queue

问题描述

解法一：模拟

用数组来模拟循环链表，用 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 这个位置，区别在于紫书是通过取余数的逻辑过来的。

#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;
}

#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;

}

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("")

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("")

AOAPC II UVaOJ 字符串