美团编程大赛第三题 优惠券 (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

© 版权声明
THE END
喜欢就支持一下吧
点赞0 分享
评论 抢沙发
头像
文明发言,共建和谐米科社区
提交
头像

昵称

取消
昵称表情图片