解题思路

食堂里有 n 种饭菜，价格按编号 1~n 存好。现在来了一个新饭菜，要插到编号 k 的位置上，它后面的所有饭菜编号都自动往后顺延一格，最后输出 n+1 个价格。

用数组解决，关键步骤是插入：

1. 先把 n 种饭菜的价格读入数组 a[1]~a[n]。
2. 读入要插入的位置 k 和新价格 x。
3. 从后往前把第 n 个到第 k 个位置的价格依次往后移一位（a[i+1]=a[i]），这样第 k 个位置就空出来了。从后往前移是为了防止覆盖还没移走的数。
4. 把新价格 x 放进第 k 个位置。
5. 输出 a[1]~a[n+1] 全部 n+1 个价格。

用样例验证：原来的价格是 20 8 10 5 ...，要在编号 3 插入价格 6，先把 10、5……全部往后移一格，再把 6 放到第 3 格，就得到 20 8 6 10 5 ...，和样例输出一致。

参考代码

// P4491 食堂管理系统：把新上架饭菜的价格按编号位置插入价格数组，再输出全部价格
#include <iostream>
using namespace std;
int a[1005];

int main() {
    int n, k, x;
    cin >> n;                  // 读入饭菜种数
    for (int i = 1; i <= n; i++) cin >> a[i];   // 读入现有每种饭菜的价格
    cin >> k >> x;             // k 是插入的编号位置，x 是新饭菜的价格
    // 从第 n 个位置往前到 k，把价格依次后移一位，腾出第 k 个位置
    for (int i = n; i >= k; i--) a[i + 1] = a[i];
    a[k] = x;                  // 新价格放入第 k 个位置
    // 输出插入后的全部价格（共 n+1 个）
    for (int i = 1; i <= n + 1; i++) cout << a[i] << ' ';
    cout << '\n';
    return 0;
}

复杂度分析

• 读入 n 个价格：O(n)。
• 插入时要移动 k 到 n 之间的元素，最坏情况（插到第 1 个位置）要移动 n 个：O(n)。
• 输出 n+1 个数：O(n)。

总时间复杂度 O(n)，空间复杂度 O(n)。