美团编程大赛第三题 优惠券 （set的应用）

时间限制：1秒
空间限制：32768K
美团点评上有很多餐馆优惠券，用户可以在美团点评App上购买。每张优惠券有一个唯一的正整数编号。当用户在相应餐馆就餐时，可以在餐馆使用优惠券进行消费。优惠券的购买和使用按照时间顺序逐行记录在日志文件中，运营人员会定期抽查日志文件看业务是否正确。业务正确的定义为：一个优惠券必须先被购买，然后才能被使用。

某次抽查时，发现有硬盘故障，历史日志中有部分行损坏，这些行的存在是已知的，但是行的内容读不出来。假设损坏的行可以是任意的优惠券的购买或者使用。

现在问这次抽查中业务是否正确。若有错，输出最早出现错误的那一行，即求出最大s，使得记录1到s-1满足要求；若没有错误，输出-1。

输入描述:
m 分别表示 m (1 ≤ 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

分析：
情况 1：该优惠券已有，找离上一个加入优惠券后的第一个问好

情况 2：该优惠券已没有，找离上一个用掉优惠券后的第一个问好

分析完上面其实只是一种情况，用cnt数组判断是否在 0~1区间内，如果不在，消除冲突即可。否则输出答案，我一开始用的多组输入，还要剪枝否则爆栈。。。大佬说是单组还观摩了一下大佬的代码。。。感觉写得太好了。。

#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> #include<set> using namespace std; const int N = 1e5+100; int vis[N],cnt[N]; set<int> st; int main() { int m; scanf("%d",&m); for(int i=1;i<=m;i++) { char op[5]; scanf(" %s",op); if(*op!='?') { int d; scanf("%d",&d); cnt[d]+=(*op=='I'?1:-1); if(cnt[d]<0||cnt[d]>1) { if(st.lower_bound(vis[d])==st.end()) { return 0*printf("%d\n",i ); } else st.erase(st.lower_bound(vis[d])); cnt[d]=max(min(cnt[d],1),0); } vis[d]=i; } else { st.insert(i); } } printf("-1\n"); } 

原文链接：https://blog.csdn.net/Littlewhite520/article/details/73410002?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522165277499316780357273335%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fblog.%2522%257D&request_id=165277499316780357273335&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~blog~first_rank_ecpm_v1~times_rank-11-73410002-null-null.nonecase&utm_term=%E4%BC%98%E6%83%A0