解题思路

书店里有 n 本图书，价格按编号 1~n 存好。现在新进一本图书，要插到编号 k 的位置，后面的图书编号顺延，最后输出 n+1 个价格。

这题和“食堂管理系统”完全一样，核心就是数组的插入操作：

1. 把 n 本图书的价格读入数组 a[1]~a[n]。
2. 读入插入位置 k 和新图书价格 x。
3. 从后往前把第 n 个到第 k 个位置的价格依次往后移一位，空出第 k 个位置。从后往前移才不会把还没移走的数覆盖掉。
4. 把新价格 x 放进第 k 个位置。
5. 输出全部 n+1 个价格。

用样例验证：原价格 200 100 39 5 ...，在编号 3 插入 45，把 39、5……全部后移，再把 45 放进去，得到 200 100 45 39 5 ...，和样例一致。

参考代码

// P4493 图书进货系统：把新上架图书的价格按编号位置插入价格数组，再输出全部价格
#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)。
• 插入时要移动元素，最多移动 n 个：O(n)。
• 输出 n+1 个数：O(n)。

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