Codeforces 749D Leaving Auction（set+二分）

骑猪看日落 2021-10-18 08:36 229阅读 0赞

## 题意：有几个人在拍卖场竞价，一共有n次喊价，有q个询问，每一个询问有一个num，接下来num个人从这次拍卖中除去，问对于每一个询问减掉num个人后是谁赢了拍卖，最小的价格是多少。 ##

## 分析：完了，水题都做不动了。。。对于每个人用 set(S) 装起来其每次喊价的下标，然后用一个数组order按价格从大到小的顺序将每个人装起来，对于每一个询问，把这num个人丢到另一个 set(s)里面，然后在order里面找没出现过在 s 里面的，那么这个人 x 就是这场拍卖的胜者，那么还要考虑他喊的最低价格，将 x 也丢到 s 里面，再找一个 y，这个 y 是第二个大的，所以在 S\[x\] 里面二分找大于 y 喊过的最大价格就是答案了。参考[https://www.cnblogs.com/fightfordream/p/6202303.html?utm\_source=itdadao&utm\_medium=referral][https_www.cnblogs.com_fightfordream_p_6202303.html_utm_source_itdadao_utm_medium_referral]。 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    const int N = 1e6+5;
    bool vis[N];
    int n,q,v[N][2];
    vector<int> order;
    set<int> S[N];
    
    int main(){
        cin >> n;
        for(int i = 0; i < n; i++) {
            scanf("%d%d", &v[i][0], &v[i][1]);
            S[v[i][0]].insert(i);
        }
        for(int i = n - 1; i >= 0; i--) {
            if(!vis[v[i][0]]) {
                vis[v[i][0]] = 1;
                order.push_back(v[i][0]);
            }
        }
        scanf("%d",&q);
        while(q--) {
            set<int> s;
            int num;
            scanf("%d", &num);
            while(num--) {
                int k;
                scanf("%d", &k);
                s.insert(k);
            }
            int x = -1, y = -1;
            for(int i = 0; i < order.size(); i++) {
                if(s.find(order[i]) == s.end()) {
                    x = order[i];
                    break;
                }
            }
            if(x == -1) printf("0 0\n");
            else {
                s.insert(x);
                for(int i = 0; i < order.size(); i++) {
                    if(s.find(order[i]) == s.end()) {
                        y = order[i];
                        break;
                    }
                }
                if(y == -1) {
                    printf("%d %d\n", x, v[*S[x].begin()][1]);
                } else {
                    set<int>::iterator it = S[y].end();
                    int pos = *(--it);
                    it = S[x].upper_bound(pos);
                    printf("%d %d\n", x, v[*it][1]);
                }
            }
        }
    }

[https_www.cnblogs.com_fightfordream_p_6202303.html_utm_source_itdadao_utm_medium_referral]: https://www.cnblogs.com/fightfordream/p/6202303.html?utm_source=itdadao&utm_medium=referral