MEGChai MEGChai
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
首页 › 数据结构与算法 › 在线评测 › UVaOJ 133 - The Dole Queue
AOAPC II

UVaOJ 133 - The Dole Queue

Chai
2021-11-24 0:00:00在线评测阅读 298

问题描述

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 这个位置,区别在于紫书是通过取余数的逻辑过来的。

C++
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;
}
Python
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("")
AOAPC II UVaOJ 字符串
赞赏 赞(0)
订阅
提醒
guest
guest
0 评论
内嵌评论
查看所有评论
  • 0
  • 0
Copyright © 2020-2023 MEGChai.
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
# 生活 # # 心理 # # 编程 # # 音乐 # # 写作 #
Chai
95
文章
4
评论
58
喜欢
wpDiscuz