P4829 草船借箭（基础）

解题思路

三国里诸葛亮草船借箭：船一字排开，每艘船一侧插满草人，射满后整艘船原地转 180 度再射另一侧。小童用纸杯模拟：3 艘船、每艘船 3 个纸杯，编号 1~9。转 180 度后每艘船里的 3 个纸杯反过来排，所以顺序变成 3 2 1 6 5 4 9 8 7。

第一步，发现规律。 纸杯一共 $3n$ 个，编号从 1 到 $3n$。每艘船有 3 个连续的编号：第 1 艘船是 1、2、3，第 2 艘是 4、5、6，第 3 艘是 7、8、9。船转 180 度后，本艘船内 3 个纸杯倒过来：3、2、1；6、5、4；9、8、7。也就是说，每个长度为 3 的小组内部反转。

第二步，怎么用栈实现？ 每艘船单独处理：把这艘船的 3 个纸杯编号依次压进一个栈，再连续出栈 3 次。因为栈“后进先出”，出栈顺序正好是这 3 个编号的倒序。处理完第 1 艘船再处理第 2 艘船，依次往下。

第三步，算第 i 艘船的编号。 第 $i$ 艘船（从 1 开始数）的 3 个纸杯编号是 $(i-1)\times3+1$、$(i-1)\times3+2$、$(i-1)\times3+3$。倒序输出就是 $(i-1)\times3+3$、$(i-1)\times3+2$、$(i-1)\times3+1$。

第四步，拿样例验证。 n=3：第 1 艘船输出 3 2 1，第 2 艘船输出 6 5 4，第 3 艘船输出 9 8 7，连起来正好是 3 2 1 6 5 4 9 8 7，和题目一致。

第五步，注意空格格式。 所有数字之间用空格隔开，最后一个数字后面换行。

第六步，为什么每艘船内部反转就够了？ 因为只有船本身转了 180 度，船与船之间的前后顺序并没有改变，第 1 艘船始终在最前面。所以我们只要把每一艘船内部的 3 个纸杯倒过来，再把所有船按顺序连起来，就是最终的答案。

参考代码

// 用途：草船借箭，n 艘船每艘 3 个纸杯，180 度调整后每组 3 个数倒序输出
#include <iostream>
using namespace std;

int main() {
    int boatCount = 0;
    cin >> boatCount;
    // 从第 1 艘船开始，逐艘处理
    for (int boat = 1; boat <= boatCount; boat++) {
        int cupStack[3];  // 每艘船只有 3 个纸杯
        int topIndex = 0;
        // 把本船的 3 个纸杯编号依次入栈
        for (int i = 0; i < 3; i++) {
            cupStack[topIndex++] = (boat - 1) * 3 + i + 1;
        }
        // 出栈，即把本船 3 个纸杯编号倒序输出
        for (int i = 0; i < 3; i++) {
            if (boat > 1 || i > 0) cout << ' ';
            cout << cupStack[--topIndex];
        }
    }
    cout << endl;
    return 0;
}

复杂度分析

n 艘船、每艘 3 个纸杯，一共 $3n$ 个纸杯。每个纸杯入栈一次、出栈一次，每次 $O(1)$，总时间 $O(n)$。空间上每艘船用一个长度 3 的小栈，是 $O(1)$。$n\le100$，非常快。