题目分析与思路提示

1. 为什么暴力法不行？

对于每个 $i$，往后循环找 $j$。如果数据是倒序排列（例如 10 9 8 ... 1），每个人都要看遍后面所有人才能确定没有比自己高的。

• 总次数 $\approx N^2/2$。
• 当 $N=10^6$ 时，运算次数高达 $5 \times 10^{11}$，远超计算机 1 秒的处理能力。

2. 核心算法：单调栈 (Monotonic Stack)

我们可以换个角度思考：在这个兵马俑寻找目标的过程中，谁是“有用”的？

假设我们从左往右遍历，维护一个栈，栈里存放还没找到仰视目标的兵马俑的编号。 这个栈里的元素，其对应的高度一定是单调递减的（如果后面来了一个高的，前面的矮个子就找到目标了，可以出栈了）。

算法流程：

1. 定义一个栈 st，用来存下标（编号）。
2. 定义一个答案数组 ans，初始化为 0。
3. 遍历每一个兵马俑 $i$（从 1 到 $N$）：
   • Check: 如果栈不为空，且当前兵马俑 $i$ 的高度 $H_i$ 大于 栈顶兵马俑的高度 $H_{st.top()}$：
     • 这意味着：栈顶那个矮个子终于等到了比他高的人（就是 $i$）！
     • 记录答案：ans[st.top()] = i。
     • 栈顶元素出栈（他的任务完成了）。
     • 重复 Check，直到栈空或栈顶比 $i$ 高（即 $i$ 挡不住栈顶了）。
   • Push: 将当前兵马俑 $i$ 入栈（等待后面比他高的人出现）。
4. 输出 ans 数组。

复杂度分析：

• 每个元素最多进栈一次。
• 每个元素最多出栈一次。
• 总操作次数是 $2N$，时间复杂度 $O(N)$。

参考代码 (C++14)

/**
 * 题目：兵马俑的军阵 (The Formation of Terracotta Warriors)
 * 难度：GESP 6级
 * 算法：单调栈 (Monotonic Stack)
 * 时间复杂度：O(N)
 */

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

// 开启 IO 优化
void fast_io() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
}

int main() {
    fast_io();

    int N;
    if (!(cin >> N)) return 0;

    vector<int> H(N + 1);
    for (int i = 1; i <= N; ++i) {
        cin >> H[i];
    }

    // ans 数组存储结果，默认初始化为 0
    vector<int> ans(N + 1, 0);
    
    // 单调栈，存储兵马俑的【编号】
    // 栈内性质：从栈底到栈顶，高度严格单调递减
    stack<int> st;

    for (int i = 1; i <= N; ++i) {
        // 当栈不为空，且当前人 i 的高度 > 栈顶人 st.top() 的高度
        // 说明 i 就是 st.top() 右边第一个比他高的人
        while (!st.empty() && H[i] > H[st.top()]) {
            int top_id = st.top();
            st.pop();
            ans[top_id] = i; // 记录答案
        }
        
        // 当前人 i 还没找到比他高的，入栈等待
        st.push(i);
    }

    // 输出结果
    for (int i = 1; i <= N; ++i) {
        cout << ans[i] << (i == N ? "" : " ");
    }
    cout << endl;

    return 0;
}

数据生成器 (Data Generator)

这是用于生成 1.in ~ 10.in 及其对应标准答案的生成器代码。

#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <string>
#include <cstdlib>
#include <ctime>
#include <algorithm>

using namespace std;

// ------------------------------------------
// 标准解法函数 (生成 .out)
// ------------------------------------------
void solve(int N, const vector<int>& H, ofstream& fout) {
    vector<int> ans(N + 1, 0);
    stack<int> st; // 存下标

    for (int i = 1; i <= N; ++i) {
        while (!st.empty() && H[i] > H[st.top()]) {
            ans[st.top()] = i;
            st.pop();
        }
        st.push(i);
    }

    for (int i = 1; i <= N; ++i) {
        fout << ans[i] << (i == N ? "" : " ");
    }
    fout << endl;
}

// 辅助函数
int randRange(int min, int max) {
    return rand() % (max - min + 1) + min;
}

int main() {
    srand(time(0));
    
    cout << "Start generating data..." << endl;

    for (int i = 1; i <= 10; ++i) {
        string in_name = to_string(i) + ".in";
        string out_name = to_string(i) + ".out";
        ofstream fin(in_name);
        ofstream fout(out_name);

        int N;
        vector<int> H;
        H.push_back(0); // 占位，让下标从1开始

        // 构造测试点
        if (i == 1) { 
            // 样例1
            N = 5;
            H.insert(H.end(), {5, 3, 1, 2, 4});
        }
        else if (i == 2) {
            // 样例2
            N = 6;
            H.insert(H.end(), {10, 9, 8, 7, 6, 11});
        }
        else if (i == 3) {
            // 递增序列 (每个人的目标都是下一个)
            N = 100;
            for(int k=1; k<=N; k++) H.push_back(k);
        }
        else if (i == 4) {
            // 递减序列 (每个人都找不到，全是0)
            N = 100;
            for(int k=N; k>=1; k--) H.push_back(k);
        }
        else if (i == 5) {
            // 锯齿形 (小 大 小 大)
            N = 1000;
            for(int k=1; k<=N; k++) H.push_back((k%2 == 1) ? 10 : 100);
        }
        else if (i == 6) {
            // 大量重复元素
            N = 2000;
            for(int k=1; k<=N; k++) H.push_back(randRange(50, 60));
        }
        else {
            // 大规模随机 (N=10^6)
            N = 1000000; 
            // H值也大一些
            for(int k=1; k<=N; k++) H.push_back(randRange(1, 1000000000));
        }

        // 写入输入
        fin << N << endl;
        for(int k=1; k<=N; k++) {
            fin << H[k] << (k==N?"":" ");
        }
        fin << endl;

        // 写入输出
        solve(N, H, fout);

        fin.close();
        fout.close();
        cout << "Generated Case " << i << endl;
    }
    
    cout << "Done!" << endl;
    return 0;
}