📝 题目大意

给定一个长度为 $N$ 的正整数数列，相邻元素不相等。反复找到第一个相邻两项差的绝对值不为 $1$ 的位置，在它们之间补全所有缺失的整数（递增或递减补全），直到所有相邻元素的差的绝对值都为 $1$。输出最终数列。

💡 解题思路

1. 题目分析：$N \le 100$，$A_i \le 100$，数据范围很小，直接模拟即可。表面上题目要求"每次找第一个差不为 1 的位置插入，然后重新扫描"，但实际上可以一次遍历完成，因为处理完当前对后，结果序列的最后一个元素恰好就是 $A_{i+1}$，不会影响后续处理。

2. 算法推导：

   • 先将 $A_0$ 放入结果数组 result。
   • 遍历 $i = 0 \sim N-2$，对于每一对 $(A_i, A_{i+1})$：
     • 若 $A_i < A_{i+1}$（上升）：依次插入 $A_i+1, A_i+2, \ldots, A_{i+1}-1$。
     • 若 $A_i > A_{i+1}$（下降）：依次插入 $A_i-1, A_i-2, \ldots, A_{i+1}+1$。
     • 最后插入 $A_{i+1}$ 本身。
   • 输出 result 数组。

3. 边界与细节：

   • 相邻两数差已经为 $1$ 时，内层循环不执行，只插入 $A_{i+1}$ 本身，不会重复插入。
   • 插入的中间值不包含端点（x < A[i+1] 或 x > A[i+1]），避免重复。
   • 题目保证 $A_i \neq A_{i+1}$，所以无需考虑相等的情况。

⏱️ 复杂度分析

• 时间复杂度：$O(N \cdot \max|A_i - A_{i+1}|)$，最坏情况下 $O(N \times 100)$，即 $O(10^4)$，完全可行。
• 空间复杂度：$O(N \cdot \max|A_i - A_{i+1}|)$，用于存储结果序列。

💻 标准代码 (C++)

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    vector<int> result;
    result.push_back(A[0]);                    // 先放入第一个元素
    for (int i = 0; i < N - 1; i++) {
        if (A[i] < A[i + 1]) {                 // 上升段：插入中间递增的数
            for (int x = A[i] + 1; x < A[i + 1]; x++) {
                result.push_back(x);
            }
        } else {                               // 下降段：插入中间递减的数
            for (int x = A[i] - 1; x > A[i + 1]; x--) {
                result.push_back(x);
            }
        }
        result.push_back(A[i + 1]);            // 插入当前对的右端点
    }
    for (size_t i = 0; i < result.size(); i++) {
        if (i > 0) cout << " ";               // 空格分隔输出
        cout << result[i];
    }
    cout << endl;
    return 0;
}