首页 > 试题广场 >

优惠券

[编程题]优惠券
  • 热度指数:244 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
美团点评上有很多餐馆优惠券,用户可以在美团点评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这些记录合法的最大行号。
示例1

输入

0
1
O 1
2
?
O 1
3
I 1
?
O 1
2
I 2
O 1

输出

-1
1
-1
-1
2
#include<iostream>
#include<map>
using namespace std;
int main(){
    long int m;
    cin>>m;
    map<int,int> Xmap;
    int flag=0;
    int Scount=0;
    for(long int i=0;i<m;i++){
        char f;
        cin>>f;
        if(f=='I'){
            int code;
            cin>>code;
            Xmap[code]++;
            if(Xmap[code]==2){
                if(Scount>0){
                    Scount--;
                    Xmap[code]--;
                }else{
                    flag=1;
                    cout<<i+1<<endl;
                    i=m;
                }
            }
        }
        if(f=='O'){
            int code;
            cin>>code;
            Xmap[code]--;
            if(Xmap[code]==-1){
                if(Scount>0){
                    Scount--;
                    Xmap[code]++;
                }else{
                    flag=1;
                    cout<<i+1<<endl;
                    i=m;
                }
            }
        }
        if(f=='?'){
            Scount++;
        }
        
    }
    if(flag==0){
        cout<<-1<<endl;
    }
    return 0;
}

百分之10通过,那个50w的数据过不去,不知道啥情况
编辑于 2019-08-22 13:44:39 回复(3)
1.题目有问题?
2.示例有问题?
3.测试有问题?
发表于 2017-08-19 21:52:34 回复(0)

热门推荐

通过挑战的用户