P4657 插队（基础）

解题思路

第一步，读懂题目。 体育课上同学们已经按身高从低到高排好了队，小童身高 h 迟到了。规则是：从队尾往前找，找到第一个"不比自己高"（身高小于等于 h）的同学，站到他的后面。因为队伍本来就是有序的，所以插队后队伍依然要从低到高。

第二步，做关键转化。 因为队伍是递增排列的，"最后一个不比自己高的人"的后面，其实就是"第一个比自己高的人"的前面。所以我们只要从头扫描一遍，找到第一个 height[i]>h 的位置 insertPos，把小童插到它的前面就行了，不必真的从队尾往前找，这样写起来更简单。

第三步，用样例验证。 队伍是 130 140 150 160 175，h=150。从队尾往前看，175、160 都比 150 高，150 不比 150 高，所以小童应该站到 150 的后面，队伍变成 130 140 150 150 160 175，仍然是从低到高有序的。

第四步，处理两种边界情况。 如果所有人都比小童高（比如队伍 170 180，h=160），小童应该站到队首；如果所有人都比小童矮或者一样高，小童站到队尾。实现时，我们先把原队伍复制到新数组 newQueue，在插入位置先放入 h，再放入原来的同学，最后一起输出 n+1 个数。

第五步，了解另一种思路。 这道题还有一种实现思路：先把小童的身高 h 追加到队伍末尾，然后从后往前不断交换，直到 h 不再比前面的同学矮为止，最终也能得到同样的结果。我们这里选择先找到插入位置、再整体复制的写法，逻辑更清晰，也更容易说清楚边界情况。核心就是利用"队伍本来有序"这个条件，用 O(n) 的时间找到正确的位置，不要用 O(n²) 的笨办法。

参考代码

// P4657 插队：把身高 myHeight 插到已按身高从低到高排好的队伍中合适位置
#include <iostream>
using namespace std;

int height[100005], newQueue[100005];

int main() {
    int n, myHeight;
    cin >> n >> myHeight;
    for (int i = 0; i < n; i++) cin >> height[i];
    // 找到第一个高于 myHeight 的位置，小童站到它前面（即最后一个不高于自己的人后面）
    int insertPos = n;
    for (int i = 0; i < n; i++) {
        if (height[i] > myHeight) {
            insertPos = i;
            break;
        }
    }
    int idx = 0;
    for (int i = 0; i < n; i++) {
        if (i == insertPos) newQueue[idx++] = myHeight; // 在 insertPos 处先插入小童
        newQueue[idx++] = height[i];
    }
    if (insertPos == n) newQueue[idx++] = myHeight; // 所有人都不高于小童，站到队尾
    for (int i = 0; i < n + 1; i++) {
        if (i > 0) cout << " ";
        cout << newQueue[i];
    }
    cout << endl;
    return 0;
}

复杂度分析

找插入位置需要扫描一遍 O(n)，复制并插入新的数组也是 O(n)，总时间 O(n)。n 即使到 10 万也非常快。空间上用了两个数组，O(n)。