首页 > 试题广场 >

优惠券

[编程题]优惠券
  • 热度指数：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
算法知识视频讲解
添加回答
面壁人10086头像 面壁人10086 
#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)
提交观点

问题信息

C++工程师 golang工程师 2017 iOS工程师 二分 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 c#工程师 美团 测试开发工程师 大数据开发工程师 Java工程师
来自：CodeM 2017美...
难度：
2条回答 4749浏览

热门推荐

通过挑战的用户

相关试题

优惠券

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号