美团编程大赛-优惠券(暴力set)

美团点评上有很多餐馆优惠券,用户可以在美团点评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
set存一发问号的位置即可。。。。。
#include<set> #include<queue> #include<vector> #include<stdio.h> #include<string.h> #include<algorithm> using namespace std; #define maxn 1000005 typedef long long ll; set<int>q; int a[maxn],b[maxn],d[maxn]; int main(void) { int m,i,x,ans,tmp; char c; while(scanf("%d",&m)!=EOF) { memset(a,0,sizeof(a)); memset(d,0,sizeof(d)); while(q.empty()==0) q.clear(); ans=-1;tmp=0; for(i=1;i<=m;i++) { scanf(" %c",&c); if(c=='?') { q.insert(i); continue; } scanf("%d",&x); if(c=='I') { if(a[x]) { set<int>::iterator it; it=q.upper_bound(a[x]); if(q.empty() || it==q.end()) { if(ans==-1) ans=i; } else q.erase(it); } a[x]=i; } if(c=='O') { if(a[x]==0) { set<int>::iterator it; it=q.upper_bound(d[x]); if(q.empty() || it==q.end()) { if(ans==-1) ans=i; } else q.erase(it); } a[x]=0; d[x]=i; } } printf("%d\n",ans); } return 0; }

原文链接:https://blog.csdn.net/haut_ykc/article/details/73302963?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-12-73302963-null-null.nonecase&utm_term=%E4%BC%98%E6%83%A0

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

昵称

取消
昵称表情图片