题目描述
美团点评上有很多餐馆优惠券，用户可以在美团点评App上购买。每种优惠券有一个唯一的正整数编号。每个人可以拥有多张优惠券，但每种优惠券只能同时拥有至多一张。每种优惠券可以在使用之后继续购买。
当用户在相应餐馆就餐时，可以在餐馆使用优惠券进行消费。某人优惠券的购买和使用按照时间顺序逐行记录在一个日志文件中，运营人员会定期抽查日志文件看业务是否正确。业务正确的定义为：一个优惠券必须先被购买，然后才能被使用。
某次抽查时，发现有硬盘故障，历史日志中有部分行损坏，这些行的存在是已知的，但是行的内容读不出来。假设损坏的行可以是任意的优惠券的购买或者使用。
现在给一个日志文件，问这个日志文件是否正确。若有错，输出最早出现错误的那一行，即求出最大s，使得记录1到s-1满足要求；若没有错误，输出-1。
输入描述:
输入包含多组数据
m 分别表示 m (0 ≤ m ≤ 5 * 10^5) 条记录。
下面有m行，格式为：
I x （I为Input的缩写，表示购买优惠券x）；
O x（O为Output的缩写，表示使用优惠券x）；
? （表示这条记录不知道）。
这里x为正整数，且x ≤ 10^5 。
输出描述:
-1 或 x(1 ≤ x ≤ m) 其中x为使得1到x-1这些记录合法的最大行号。
输入例子:
0 1 O 1 2 ? O 1 3 I 1 ? O 1 2 I 2 O 1
输出例子:
-1 1 -1 -1 2
ac代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<vector> 5 #include<algorithm> 6 #include<cmath> 7 #include<set> 8 using namespace std; 9 const int maxn = 1e5 + 100; 10 int num[maxn * 5]; 11 int n; 12 13 int main() 14 { 15 char s[10]; 16 while (~scanf("%d", &n)) 17 { 18 set<int>Q; 19 int ans; 20 int ok = 0; 21 set<int>::iterator it; 22 for (int i = 0;i<n;i++) 23 { 24 scanf("%s", s); 25 if (s[0] == '?') 26 { 27 Q.insert(i + 1); 28 } 29 else if (s[0] == 'I') 30 { 31 int tmp; 32 scanf("%d", &tmp); 33 if (ok) 34 continue; 35 if (num[tmp]>0) 36 { 37 it = Q.lower_bound(num[tmp]); 38 if (it != Q.end()) 39 { 40 Q.erase(it++); 41 } 42 else 43 { 44 if (ok == 0) { 45 ok = 1; 46 ans = i + 1; 47 } 48 } 49 } 50 num[tmp] = i + 1; 51 } 52 else 53 { 54 int tmp; 55 scanf("%d", &tmp); 56 if (ok) 57 continue; 58 if (num[tmp] <= 0) 59 { 60 it = Q.lower_bound(-num[tmp]); 61 if (it != Q.end()) 62 { 63 Q.erase(it++); 64 } 65 else 66 { 67 if (ok == 0) { 68 ok = 1; 69 ans = i + 1; 70 } 71 } 72 } 73 num[tmp] = -(i + 1); 74 75 } 76 } 77 if (ok) 78 { 79 cout << ans << endl; 80 } 81 else 82 { 83 cout << -1 << endl; 84 } 85 } 86 }