题解：AT_abc448_c [ABC448c] Except and Min

· · 题解

思路

不难发现，答案必在按权值排序的前 K + 1 小的球中。因为即使前 K 小的球全部被移除，第 K + 1 小的球也一定会留在袋中成为最小值。

实现也很简单：

  1. 将所有球按照权值 A_i 从小到大排序，注意需要记录它们原始的编号（因为删除时用的是原始编号）。
  2. 对于每个询问，我们从排序后的数组从头开始遍历，并判断如果该球的编号不在列表中，它就是答案，否则就继续遍历。

最后算一下时间复杂度，排序的时间复杂度是 O(N \log N)，查询的时间复杂度总共为 O(Q \times K ^ 2)。整个代码的时间复杂度就是 O(N \log N + Q \times K ^ 2)，可以通过。

代码

#include <bits/stdc++.h>
using namespace std;
struct node{
    int id, val;
}a[300005];
int n, q;
int b[10];
bool cmp(node x, node y){
    return x.val < y.val;
}
int main(){
    cin >> n >> q;
    for(int i = 1; i <= n; i++){
        cin >> a[i].val;
        a[i].id = i;
    }  
    sort(a + 1, a + n + 1, cmp);

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

        for(int i = 1; i <= n; i++){
            bool flag = true;
            for(int j = 1; j <= k; j++){
                if(b[j] == a[i].id){
                    flag = false;
                    break;
                }
            }

            if(flag == true){
                cout << a[i].val << '\n';
                break;
            }
        }       
    }                                      
}