C26L:Stack Sort

http://poj.openjudge.cn/practice/C26L/

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while (T--) {
        int n;
        cin >> n;

        vector<vector<int>> st(n + 1);
        vector<int> pos(n + 1);

        for (int x = 1; x <= n; x++) {
            int a;
            cin >> a;
            st[a].push_back(x);
            pos[x] = a;
        }

        vector<int> ans;
        ans.reserve(6 * n + 5);

        auto operate = [&](int i) {
            int k = (int)st[i].size();
            int x = st[i].back();
            st[i].pop_back();
            st[k].push_back(x);
            pos[x] = k;
            ans.push_back(i);
        };

        auto make_room = [&](int k) {
            if (k <= 1) return;

            if ((int)st[k].size() <= k - 2) return;

            int j = k;
            while (j >= 2 && (int)st[j].size() == j - 1) {
                j--;
            }

            // 对有解数据，j 一定不会降到 1。
            // 否则意味着在 1 进栈 1 之前必须先把别的元素放进栈 1，最终无解。
            for (int x = j + 1; x <= k; x++) {
                operate(x);
            }
        };

        // Phase 1: 如果元素 1 不在栈 1，先安全地把它送到栈 1。
        if (pos[1] != 1) {
            int p = pos[1];

            while (pos[1] != 1) {
                int k = (int)st[p].size();

                if (k > 1) {
                    make_room(k);
                }

                operate(p);
            }
        }

        // Phase 2: 把所有非 1 号栈的元素收集到栈 1。
        // 此时栈 1 的底部一定是元素 1。
        for (int i = 2; i <= n; i++) {
            while (!st[i].empty()) {
                int k = (int)st[i].size();

                operate(i);

                if (k > 1) {
                    operate(k);
                }
            }
        }

        // Phase 3: 当前所有元素都在栈 1，且元素 1 在栈底。
        // 先把除 1 外的元素弹出去，记录每个元素去了哪个栈。
        vector<int> where(n + 1, 0);

        while ((int)st[1].size() > 1) {
            int k = (int)st[1].size();
            int x = st[1].back();

            operate(1);
            where[x] = k;
        }

        // 按 2,3,...,n 的顺序把它们放回栈 1。
        // 这样栈 1 从底到顶变成 1,2,3,...,n。
        for (int x = 2; x <= n; x++) {
            operate(where[x]);
        }

        // 最后从栈 1 分发到对应编号的栈。
        while ((int)st[1].size() > 1) {
            operate(1);
        }

        cout << ans.size() << '\n';
        for (int i = 0; i < (int)ans.size(); i++) {
            if (i) cout << ' ';
            cout << ans[i];
        }
        cout << '\n';
    }

    return 0;
}

这是一个关于栈排序（Stack Sorting）的构造算法题。题目给定 $n$ 个栈，初始时每个栈中可能有一些元素。我们的目标是通过特定的移动操作，使得最终元素 $i$ 位于栈 $i$ 中。

题目逻辑与算法步骤解读

这道题的操作规则非常特殊：调用 operate(i) 时，会将栈 $i$ 顶部的元素弹出，并压入栈 $k$ 中，其中 $k$ 是弹出前栈 $i$ 的高度。

代码通过三个阶段（Phases）构造解：

1. 第一阶段：送 1 归位

   • 我们要把元素 1 送到栈 1 的底部。
   • 如果元素 1 当前在栈 $p$ 且不在底部（高度 $>1$），我们需要腾出空间（make_room），然后不断执行 operate(p)。
   • 根据规则，当栈 $p$ 的高度为 1 时，弹出的元素会进入栈 1。

2. 第二阶段：全员集合到栈 1

   • 通过巧妙的二次移动，将所有非 1 元素都收集到栈 1。
   • 如果元素在高度为 $k$ 的栈 $i$ 顶部：
     • 若 $k=1$，执行 operate(i)，元素直接去栈 1。
     • 若 $k>1$，执行 operate(i) 元素去栈 $k$；此时栈 $k$ 的高度变为 1，紧接着执行 operate(k)，元素就会去栈 1。

3. 第三阶段：栈内排序与分发

   • 现在所有元素都在栈 1，底部是 1。
   • 由于栈 1 的高度在不断变化，我们先将元素 $2\sim n$ 依次弹出到临时栈中，并记录它们去的栈编号 where[x]。
   • 按照 $2,3,\dots ,n$ 的顺序将它们导回栈 1，此时栈 1 从底到顶变为 $1,2,3,\dots ,n$。
   • 最后，再次依次弹出栈 1 顶部的元素。由于弹出元素 $i$ 时，栈 1 的高度正好是 $i$，所以元素 $i$ 会准确进入栈 $i$。

---

Python 代码实现

import sys

def solve():
    # 使用 sys.stdin.read().split() 快速读取大数据
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    it = iter(input_data)
    
    t_cases = int(next(it))
    for _ in range(t_cases):
        n = int(next(it))
        # st[i] 存储第 i 个栈的元素
        st = [[] for _ in range(n + 1)]
        # pos[x] 存储元素 x 当前所在的栈编号
        pos = [0] * (n + 1)
        
        for x in range(1, n + 1):
            a_idx = int(next(it))
            st[a_idx].append(x)
            pos[x] = a_idx
            
        ans = []
        
        def operate(i):
            """执行题目定义的移动操作"""
            k = len(st[i])
            if k == 0: return # 防护
            x = st[i].pop()
            # 移动到高度为 k 的栈
            st[k].append(x)
            pos[x] = k
            ans.append(i)

        def make_room(k):
            """当栈 k 太满时，通过循环移动腾出空间"""
            if k <= 1: return
            # 如果栈 k 还有多余位置，不需要操作
            if len(st[k]) <= k - 2: return
            
            j = k
            # 寻找下方第一个没满的栈
            while j >= 2 and len(st[j]) == j - 1:
                j -= 1
            # 依次向下挪动一位
            for x in range(j + 1, k + 1):
                operate(x)

        # Phase 1: 确保元素 1 在栈 1 的最底部
        if pos[1] != 1:
            p = pos[1]
            while pos[1] != 1:
                k_size = len(st[p])
                if k_size > 1:
                    make_room(k_size)
                operate(p)

        # Phase 2: 将所有其他元素收集到栈 1
        for i in range(2, n + 1):
            while st[i]:
                k_size = len(st[i])
                operate(i)
                if k_size > 1:
                    operate(k_size)

        # Phase 3: 在栈 1 内部实现 1,2,3...n 的排序
        where = [0] * (n + 1)
        while len(st[1]) > 1:
            k_size = len(st[1])
            top_val = st[1][-1]
            operate(1)
            where[top_val] = k_size
        
        # 按照 2..n 的顺序导回栈 1
        for x in range(2, n + 1):
            operate(where[x])
            
        # 最后分发：依次弹出，高度为 i 的元素会进入栈 i
        while len(st[1]) > 1:
            operate(1)
            
        # 输出操作总数和具体步骤
        sys.stdout.write(f"{len(ans)}\n")
        if ans:
            sys.stdout.write(" ".join(map(str, ans)) + "\n")
        else:
            sys.stdout.write("\n")

if __name__ == "__main__":
    solve()

---

关键点总结

1. 规则利用：本题的关键是意识到“弹出位置取决于当前栈的高度”。Phase 2 的双跳（operate(i) 然后 operate(k)）是核心技巧。
2. 构造思想：当直接移动很困难时，先将所有元素汇聚到一个中转站（栈 1），在已知顺序的情况下再分发。
3. Python 效率：
   • 使用 sys.stdin.read().split() 避免频繁的 IO 阻塞。
   • 使用 sys.stdout.write 代替 print 以加快输出。
   • 虽然 Python 性能不如 C++，但由于该算法的时间复杂度是线性的 $O(N)$，且操作步数限制在 $6N$ 左右，因此在合理的时限内完全可以运行。
4. 边界处理：make_room 函数保证了在移动过程中不会因为目标栈已满而导致死锁或非法操作。