c/c++语言开发共享LOJ#6085. 「美团 CodeM 资格赛」优惠券(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; }