欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

LOJ#6085. 「美团 CodeM 资格赛」优惠券(set)

程序员文章站 2022-03-02 23:44:32
题意 "题目链接" Sol 考虑不合法的情况只有两种: 1. 进去了 再次进去 2. 没进去 但是出来了 显然可以用未知记录抵消掉 直接开个set维护一下所有未知记录的位置 最优策略一定是最后一次操作位置的后继 同时我们需要记录一下每个人是否在里面 ......

题意

sol

考虑不合法的情况只有两种:

  1. 进去了 再次进去

  2. 没进去 但是出来了

显然可以用未知记录抵消掉

直接开个set维护一下所有未知记录的位置

最优策略一定是最后一次操作位置的后继

同时我们需要记录一下每个人是否在里面

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int m, las[maxn], op[maxn];//las上一次进去的时间  op最后一次操作的位置 
set<int> ms;
signed main() {
    //freopen("a.in", "r", stdin);
    m = read();
    for(int i = 1; i <= m; i++) {
        char c = 'g';
        while(c != 'i' && c != 'o' && c != '?') c = getchar();
        if(c == 'i') {
            int x = read();
            if(las[x]) {//在里面 
                auto pos = ms.upper_bound(op[x]);
                if(pos == ms.end() || (*pos > i)) return printf("%d", i), 0;
                else ms.erase(pos);
            }
            las[x] = 1;
            op[x] = i;
        } else if(c == 'o') {
            int x = read();
            if(!las[x]) {
                auto pos = ms.upper_bound(op[x]);
                if(pos == ms.end() || (*pos > i)) return printf("%d", i), 0;
                else ms.erase(pos);
            }
            las[x] = 0;
            op[x] = i;
        } else ms.insert(i);
        c = 'g';
    }
    puts("-1");
    return 0;
}