解题思路

帝国管理者用数组记录 n 名士兵的武力值，有两种操作：

• 输入 0：插入士兵。读入编号 k 和新武力值 x，把 x 插到第 k 个位置，后面的武力值往后顺延，最后输出 n+1 个武力值。
• 输入 1：抽离士兵。读入编号 k，把第 k 个士兵的武力值删掉，后面的武力值往前补上来，最后输出 n-1 个武力值。

插入的做法和食堂管理系统一样：从最后一个位置开始，把第 n 个到第 k 个位置的武力值依次往后移一位，再把新武力值放到第 k 个位置。从后往前移动可以避免覆盖还没移动的数据。

删除的做法恰好相反：从第 k 个位置开始，把后面的武力值依次往前移一位（a[i]=a[i+1]），这样第 k 个位置的武力值就被后面的覆盖掉，相当于删除了。数组长度从 n 变成 n-1。

因为插入后数组最多有 n+1 个数，所以数组要开得比 n 稍大一些（代码里开到 2005），防止越界。

用样例验证：插入到编号 4 位置武力值 145，把 150、76……往后移，再放 145，得到 199 100 190 145 150 ...，与样例一致。

参考代码

// P4492 超级队伍：输入 0 表示在指定位置插入士兵武力值，输入 1 表示删除指定位置的士兵武力值
#include <iostream>
using namespace std;
int a[2005];

int main() {
    int n, op;
    cin >> n;                  // 读入士兵数量
    for (int i = 1; i <= n; i++) cin >> a[i];   // 读入每名士兵的武力值
    cin >> op;                 // 读入操作：0 插入，1 删除
    if (op == 0) {             // 情况一：插入士兵
        int k, x;
        cin >> k >> x;         // k 是插入位置，x 是新士兵的武力值
        // 从第 n 个位置往前到 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] << ' ';
    } else {                   // 情况二：删除士兵
        int k;
        cin >> k;              // k 是要删除的士兵编号
        // 从第 k 个位置开始，后面的武力值依次前移一位，覆盖掉要删除的
        for (int i = k; i < n; i++) a[i] = a[i + 1];
        // 输出剩下的 n-1 个武力值
        for (int i = 1; i <= n - 1; i++) cout << a[i] << ' ';
    }
    cout << '\n';
    return 0;
}

复杂度分析

• 插入：从 n 到 k 移动元素，最多移动 n 个：O(n)。
• 删除：从 k 到 n 前移元素，最多移动 n 个：O(n)。
• 输出：O(n)。

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