[语言月赛 202507] 卡牌游戏的题解

记住只在没有思路时使用题解，不要从它复制粘贴代码。请尊重题目和题解的作者。
在解题之前提交题解的代码会导致封禁。

作者： admin

概述

给定一副从顶到底为 $a_1, a_2, \ldots, a_n$ ~a_1, a_2, \ldots, a_n~ 的牌（是 $1 \sim n$ ~1 \sim n~ 的一个排列）与参数 $k$ ~k~。洗牌规则是：先按 $k$ ~k~ 把牌堆切成上堆 A（前 $k$ ~k~ 张）与下堆 B（后 $n-k$ ~n-k~ 张），再从 A 开始轮流取两堆顶部的牌追加到新牌堆的底部，直到有一堆被取空，最后把另一堆剩下的牌按原顺序整段接到新牌堆底部。全体操作没有任何随机性，本质是把原数组按下标重新排布，因此只需用两个下标在原数组上顺序扫描一遍即可，时间 $O(n)$ ~O(n)~。

分析

核心观察

整个过程是完全确定的：每一轮依次取 A 顶、B 顶各一张，先 A 后 B，写成序列就是 $A_1, B_1, A_2, B_2, \ldots$ ~A_1, B_1, A_2, B_2, \ldots~。

因此，输出牌的来源可以被拆成两段：

交错段：一共进行 $\min(k, n-k)$ ~\min(k, n-k)~ 轮，每轮写 2 张牌，故前 $2\min(k,n-k)$ ~2\min(k,n-k)~ 张牌恰好是 A、B 两堆从顶部开始的一一交错；
收尾段：轮数走到 $\min(k,n-k)$ ~\min(k,n-k)~ 时，短的那一堆恰好被取空，长的那一堆剩下的牌在各自数组里仍是一段连续区间，按原顺序整段接上即可。

关键点是：新牌堆只做“追加到末尾”这一种操作，所以完全不需要真的用队列去模拟“取顶 / 压底”——新牌堆的内容就是原数组按下标重排的结果，“取出的牌依次追加”与“按同样次序直接读取原数组”是同一件事。收尾段也可以直接照抄：若 $k \le n-k$ ~k \le n-k~，B 的剩余就是下标 $2k \sim n-1$ ~2k \sim n-1~ 的连续一段；若 $k > n-k$ ~k > n-k~，A 的剩余就是下标 $n-k \sim k-1$ ~n-k \sim k-1~ 的连续一段。

两个退化情形可以直接看出来： $k = n$ ~k = n~ 时 B 是空堆，一次都不取，输出与原牌堆相同； $k = 1$ ~k = 1~ 时交错一轮后 A 即被取空，B 的剩余恰好是原来的第 $2 \sim n$ ~2 \sim n~ 张，输出同样与原牌堆相同。另外当 $k = n/2$ ~k = n/2~（ $n$ ~n~ 为偶数）时两堆等长，没有收尾段，输出是严格的完美交错。

思路

把数组下标当成两个游标： $i$ ~i~ 指向 A 的顶部（初始 $i = 0$ ~i = 0~）， $j$ ~j~ 指向 B 的顶部（初始 $j = k$ ~j = k~，即输入的第 $k+1$ ~k+1~ 张牌）。只要两堆都还有牌，就交替写出 $a_i$ ~a_i~ 和 $a_j$ ~a_j~，然后两个游标同时后移一格；退出循环时至少有一堆已被取空（更准确地说，恰好是短的那一堆），把两个游标各自尚未走到头的部分按原顺序追加即可。

用公式描述，记 $m = \min(k, n-k)$ ~m = \min(k, n-k)~，答案数组 $c$ ~c~ 为

$\displaystyle c_{2t} = a_t,\quad c_{2t+1} = a_{k+t} \qquad (0 \le t < m)$

其后：

若 $k \le n-k$ ~k \le n-k~（B 不短于 A）： $c_{2m+s} = a_{2m+s}$ ~c_{2m+s} = a_{2m+s}~，其中 $0 \le s < n-2m$ ~0 \le s < n-2m~，即下标 $2k \sim n-1$ ~2k \sim n-1~ 的牌原地不动；
若 $k > n-k$ ~k > n-k~（A 更长）： $c_{2m+s} = a_{m+s}$ ~c_{2m+s} = a_{m+s}~，其中 $0 \le s < 2k-n$ ~0 \le s < 2k-n~，即把 A 中还没取的牌依次接上。

下面两件事保证了游标做法的正确性：一是每轮取牌的先后顺序固定为 A、B，所以交错段的写法和公式一致；二是循环结束时不可能两堆同时还有牌（取空一轮就停），所以收尾时至多只有一段需要追加，且追加的牌本来就在原数组里连续存放、顺序不变，与题面“将仍剩余卡牌的牌堆的所有牌按原顺序放到新牌堆的底部”完全吻合。

顺带一提，也可以完全按题面字面用双端队列逐张模拟（见文末 Python 参考实现）：每张牌只经历一次“取队首、压队尾”，单步代价 $O(1)$ ~O(1)~，总复杂度同样是 $O(n)$ ~O(n)~，两种写法互为对拍。

具体示例

样例 1： $n = 6$ ~n = 6~， $k = 2$ ~k = 2~，牌堆为 $1, 2, 3, 4, 5, 6$ ~1, 2, 3, 4, 5, 6~。此时 A 为 $\{1,2\}$ ~\{1,2\}~，B 为 $\{3,4,5,6\}$ ~\{3,4,5,6\}~， $\min(k, n-k) = 2$ ~\min(k, n-k) = 2~，交错段为 $1, 3$ ~1, 3~ 与 $2, 4$ ~2, 4~ 共两轮；随后 A 已空，B 还剩 $5, 6$ ~5, 6~（下标 $2k = 4 \sim 5$ ~2k = 4 \sim 5~ 的牌，确实原地不动），整段接上得 $1, 3, 2, 4, 5, 6$ ~1, 3, 2, 4, 5, 6~。

样例 2： $n = 7$ ~n = 7~， $k = 1$ ~k = 1~，牌堆为 $1, 5, 2, 3, 6, 7, 4$ ~1, 5, 2, 3, 6, 7, 4~。A 为 $\{1\}$ ~\{1\}~，B 为 $\{5, 2, 3, 6, 7, 4\}$ ~\{5, 2, 3, 6, 7, 4\}~，交错一轮得 $1, 5$ ~1, 5~；此时 A 被取空，B 的剩余 $2, 3, 6, 7, 4$ ~2, 3, 6, 7, 4~ 接上，结果为 $1, 5, 2, 3, 6, 7, 4$ ~1, 5, 2, 3, 6, 7, 4~，与原牌堆完全相同——正对应前面指出的 $k = 1$ ~k = 1~ 时洗牌是恒等变换。

样例 3： $n = 12$ ~n = 12~， $k = 6$ ~k = 6~，牌堆为 $10, 7, 9, 5, 11, 6, 12, 8, 4, 3, 2, 1$ ~10, 7, 9, 5, 11, 6, 12, 8, 4, 3, 2, 1~。两堆等长：A 为 $10, 7, 9, 5, 11, 6$ ~10, 7, 9, 5, 11, 6~，B 为 $12, 8, 4, 3, 2, 1$ ~12, 8, 4, 3, 2, 1~，一共 6 轮、没有收尾段，输出是严格交错 $10, 12, 7, 8, 9, 4, 5, 3, 11, 2, 6, 1$ ~10, 12, 7, 8, 9, 4, 5, 3, 11, 2, 6, 1~。

算法步骤

读入 $n, k$ ~n, k~，再读入 $n$ ~n~ 个整数存入数组 $a$ ~a~（下标从 0 开始）。
置游标 $i = 0$ ~i = 0~（A 顶）与 $j = k$ ~j = k~（B 顶），答案数组 $c$ ~c~ 置空。
当 $i < k$ ~i < k~ 且 $j < n$ ~j < n~ 时循环：把 $a_i$ ~a_i~ 追加到 $c$ ~c~ 末尾，再把 $a_j$ ~a_j~ 追加到 $c$ ~c~ 末尾，然后令 $i \gets i + 1$ ~i \gets i + 1~、 $j \gets j + 1$ ~j \gets j + 1~。
循环结束后追加尚未取完的部分：只要 $i < k$ ~i < k~ 就依次追加 $a_i, a_{i+1}, \ldots, a_{k-1}$ ~a_i, a_{i+1}, \ldots, a_{k-1}~；只要 $j < n$ ~j < n~ 就依次追加 $a_j, a_{j+1}, \ldots, a_{n-1}$ ~a_j, a_{j+1}, \ldots, a_{n-1}~。这两段至多只有一段非空。
把 $c$ ~c~ 的 $n$ ~n~ 个元素按空格分隔成一行输出。

复杂度分析

时间： $O(n)$ ~O(n)~。交错阶段共 $\min(k, n-k)$ ~\min(k, n-k)~ 轮、每轮写 2 张牌，收尾阶段把剩余牌各写一次，每张牌恰好写入 $c$ ~c~ 一次，单张牌的处理只含一次读取、一次写入和常数次下标自增。
空间： $O(n)$ ~O(n)~，用于保存输入数组与答案数组。若改成原地重排可以压到 $O(1)$ ~O(1)~ 额外空间，但题面限制 $n \le 2000$ ~n \le 2000~，直接开数组更清晰，也没有必要优化。
即使用队列按题面逐张模拟，取队首与压队尾都是 $O(1)$ ~O(1)~ 的，总时间仍是 $O(n)$ ~O(n)~，这也是题面数据范围内完全可行的做法。

实现注意事项

循环条件要用“两个游标是否都还没到头”来判断，不要写成固定的 $k$ ~k~ 轮、 $n$ ~n~ 轮或 $n/2$ ~n/2~ 轮：轮数应当是 $\min(k, n-k)$ ~\min(k, n-k)~，写错会漏牌或多取牌。
B 的队首在 0 下标数组里是 a[k]（输入的第 $k+1$ ~k+1~ 张牌）；若误写成 a[k-1]，会把 A 的最后一张牌重复取出一次。
收尾的两段不必先判断谁长谁短：循环退出时短的那堆必然已经取空（取空长度恰为 $\min(k,n-k)$ ~\min(k,n-k)~），因此“两段都无条件追加”的写法天然正确，也省去了分类讨论。
“剩余牌堆整段接上”与“继续一张一张取下去”结果相同——因为整段接上只是把同一段牌按同样顺序追加，这一点本身就是循环退出条件的由来，不需要再单独模拟。
退化情形无需特判： $k = n$ ~k = n~ 时循环体一次不执行，输出就是原牌堆； $k = 1$ ~k = 1~ 时同样输出原牌堆； $n = 1$ ~n = 1~ 时唯一合法的输入是 $k = 1$ ~k = 1~，输出那张牌本身。
卡牌编号是 $1 \sim n$ ~1 \sim n~ 的排列，值域很小，int 完全够用，也不存在需要去重的情况。
输出是一行 $n$ ~n~ 个空格分隔的整数，行末换行使输出更规范；多数判题器忽略行末空白，但不依赖这一点。
C++ 里用 scanf/printf 或 cin/cout 都可以，本题输入输出规模（ $n \le 2000$ ~n \le 2000~）远小于需要关同步的级别。

源代码

#include <cstdio>
#include <vector>

int main() {
    int n, k;
    if (scanf("%d %d", &n, &k) != 2) return 0;

    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) scanf("%d", &a[i]);

    // 分堆：A = a[0..k-1]，B = a[k..n-1]，两者都是「顶到底」的顺序。
    // 从 A 开始轮流取各自顶部放到新牌堆底部；任一牌堆抽空后，把另一堆
    // 剩下的牌按原顺序整段接上去——注意「整段接上」等价于「多取一张后
    // 再接剩余」，因为多取的那张本来就是剩余段的队首。
    std::vector<int> c;
    c.reserve(n);

    int i = 0, j = k;
    while (i < k && j < n) {
        c.push_back(a[i++]);
        c.push_back(a[j++]);
    }
    while (i < k) c.push_back(a[i++]);
    while (j < n) c.push_back(a[j++]);

    for (int t = 0; t < n; ++t) printf("%d%c", c[t], t + 1 == n ? '\n' : ' ');
    return 0;
}

import sys
from collections import deque


def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    k = int(data[1])
    a = list(map(int, data[2:2 + n]))

    # 按题面字面模拟：A = 前 k 张，B = 其余；从 A 开始轮流取各堆顶部，
    # 追加到新牌堆底部；一堆空了就把另一堆剩下的整段接上。
    pile_a = deque(a[:k])
    pile_b = deque(a[k:])
    new_pile = deque()
    take_a = True
    while pile_a and pile_b:
        new_pile.append(pile_a.popleft() if take_a else pile_b.popleft())
        take_a = not take_a
    new_pile.extend(pile_a if pile_a else pile_b)

    sys.stdout.write(" ".join(map(str, new_pile)) + "\n")


if __name__ == "__main__":
    main()

目前没有评论。