ACM 線性表操作：題目大意與解題思路

題目來源

ACM 題庫「線性表操作」，時間限制 1000MS，內存 65536KB。

題目大意（重構）

實現一個線性表（序列），支持以下操作：
1. 插入：在指定位置插入元素。
2. 刪除：刪除指定位置元素。
3. 查找：按值或位置查找。
4. 修改：更新指定位置元素值。
5. 輸出：順序輸出所有元素。
輸入包含多組測試數據，每組以操作序列形式給出，要求正確處理邊界條件（越界、空表等）。

數據結構選擇

• 順序表（動態數組）：隨機訪問 O(1)，插入刪除 O(n)，適合查找多、修改少場景。
• 鏈表：插入刪除 O(1)（已定位），查找 O(n)，適合頻繁增刪場景。
• C++ STL vector / list：現代 C++ 首選，自動管理內存，介面豐富。

核心操作實現（以 vector 為例）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m; // n: 初始長度, m: 操作數
    while (cin >> n >> m) {
        vector a(n);
        for (int i = 0; i < n; ++i) cin >> a[i];
        for (int opIdx = 0; opIdx < m; ++opIdx) {
            string op; cin >> op;
            if (op == "INSERT") {
                int pos, val; cin >> pos >> val;
                if (pos >= 0 && pos <= (int)a.size())
                    a.insert(a.begin() + pos, val);
            } else if (op == "DELETE") {
                int pos; cin >> pos;
                if (pos >= 0 && pos < (int)a.size())
                    a.erase(a.begin() + pos);
            } else if (op == "FIND") {
                int val; cin >> val;
                auto it = find(a.begin(), a.end(), val);
                cout << (it != a.end() ? distance(a.begin(), it) : -1) << '\n';
            } else if (op == "UPDATE") {
                int pos, val; cin >> pos >> val;
                if (pos >= 0 && pos < (int)a.size())
                    a[pos] = val;
            } else if (op == "PRINT") {
                for (size_t i = 0; i < a.size(); ++i) {
                    if (i) cout << ' ';
                    cout << a[i];
                }
                cout << '\n';
            }
        }
    }
    return 0;
}

常見坑點

• 位置索引是 0-based 還是 1-based，題目需仔細讀輸入說明。
• 插入位置可等於 size()（尾插），刪除位置必須 < size()。
• 多組測試用例，注意清空容器或重新聲明。
• 大數據量下 vector 頻繁中間插刪可能 TLE，可改用 list 或塊狀鏈表。