CodeM资格赛 优惠券

[编程|1000分] 优惠券

时间限制：1秒
空间限制：32768K

题目描述

美团点评上有很多餐馆优惠券，用户可以在美团点评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
开始想的太简单了，直接用num存下?出现过的次数，然后在要用到？的时候再判断是否还有？，结果果然错了
后来想了一下，发现了很多特殊情况。比如
4 I 1 ? ? I 1 
4 I 1 ? O 1 O 1
还要注意下题意，输入两个或以上同样的优惠券也不行
参考博客
http://blog.csdn.net/w571523631/article/details/73250025#

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <set>
using namespace std;
#define maxn 100010
int num[maxn]; 
int main()
{
    int n;
    while(cin >> n)
    {
        memset(num,0,sizeof(num));
        set<int> q;
        set<int>::iterator it;
        int ans , flag = 0;
        for(int i=1;i<=n;i++)
        {
            char c;
            cin >> c;
            if(c == '?')
            {
                q.insert(i);//记录？出现的行数，用来在后面要用？时判断是否可以用或用哪一个
                continue;
            }
            int t;
            cin >> t;
            if(c == 'I')
            {
                if(flag)
                    continue;
                if(num[t] >= 1)
                {
                    it = q.lower_bound(num[t]);//查找低于或等于此行的？
                    if(it!=q.end())
                        q.erase(it);
                    else
                    {
                        if(!flag)
                        {
                            flag = 1;
                            ans = i;
                        }
                    }
                }
                num[t] = i;
            }
            else 
            {
                if(flag)
                    continue;
                if(num[t] <= 0)//注意这里取到了零，num[t]等于零时也要判断
                {
                    it = q.lower_bound(-num[t]);
                    if(it!=q.end())
                        q.erase(it);
                    else 
                    {
                        if(!flag)
                        {
                            flag = 1;
                            ans = i;
                        }
                    }
                }
                num[t] = -i;//这里取负数，节省了空间，道理一样
            }
        }
        if(flag)
            cout << ans << endl;
        else cout << "-1" << endl; 
    }
    return 0;
}