题解：AT_abc448_c [ABC448C] Except and Min

AndyHolmes · 2026-03-10 08:23:23 · 题解

思路

第一种做法

直接使用 multiset 进行模拟。

multiset 天生支持插入数字和删除迭代器的操作，时间复杂度都是 O(\log N)。

每次询问时：

1. 读入需要删除的 K 个球的编号。
2. 将对应的 A_{B_i} 从 multiset 中删除。
3. 此时 *s.begin() 就是当前袋子中的最小值。
4. 输出答案后，再将删除的元素重新插入 multiset 中。

代码

#include <bits/stdc++.h>

using namespace std;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int n, q;
    cin >> n >> q;

    vector<int> a(n);
    multiset<int> s;

    for (int i = 0; i < n; i++) {
        cin >> a[i];
        s.insert(a[i]);
    }

    while (q -- ) {
        int k;
        cin >> k;
        vector<int> b(k);
        for (int i = 0; i < k; i++) {
            cin >> b[i]; b[i] -- ;
            s.erase(s.find(a[b[i]]));
        }
        cout << *s.begin() << '\n';
        for (int i = 0; i < k; i++) s.insert(a[b[i]]);
    }

    return 0;
}

时间复杂度：

第二种做法

由于题目给定的 K 最大为 5，数值较小。而且删除 K 个球后，最小值一定出现在原数组中前 K+1 小的数里。

因此可以先将 A 数组按数值排序，并记录每个数原来的下标。
对于每次询问，只需要在排序后的前 K+1 个元素中找到一个下标不在 B 数组中的元素就行，这个元素对应的值就是答案。

判断某个下标是否在 B 数组中，可以使用 find 进行线性查找。因为 K \le 5，复杂度还是比较小。

代码:

#include <bits/stdc++.h>

using namespace std;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int n, q;
    cin >> n >> q;

    vector<pair<int, int>> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i].first;
        a[i].second = i + 1;
    }

    sort(a.begin(), a.end());

    while (q -- ) {
        int k;
        cin >> k;
        vector<int> b(k);
        for (int i = 0; i < k; i++) cin >> b[i];

        for (int i = 0; i < 6; i++) {
            if (find(b.begin(), b.end(), a[i].second) == b.end()) {
                cout << a[i].first << '\n';
                break;
            }
        }
    }

    return 0;
}

时间复杂度：