时间限制: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
暂无评论内容