美团资格赛题解：3

03:12 Jun.17-2017

美团点评上有很多餐馆优惠券，用户可以在美团点评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这些记录合法的最大行号。

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

输入例子:

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

输出例子:

-1
1
-1
-1
2

思路

初步思路

拿到这道题，被前两题惯坏又很naive的我没有进行过多考虑就想出了如下思路：

从上往下处理数据，处理过程中记录下‘?’的数量和各种优惠券的数量，每当发生冲突（即某种优惠券的数量变为2或者-1）时，就去消费一个‘?’，直到‘?’数量为0时代表发生了错误。结果只过了10%的样例。

考虑问号的位置

经过仔细思考，我发现这道题没那么简单，如输入依次为?，I 1, I 1时，按理说‘?’不可能将两个“I 1”的冲突抵消，由此，我们需要考虑问号和两个冲突的记录的位置，即问号必须在两个冲突记录之间才能消费，基于贪心策略，我将算法修改如下：

从上往下处理数据，处理过程中使用一颗查找树记录下‘?’的位置（c++中的set正合适）和各种优惠券最近一次发生I，O操作的行号（使用两个大小为10^5的数组I, O来存储，初始均为-1），当处理“I x”时，检查上一个“I x”是否在上一个“O x”之前（或等于，代表I[x]，O[x]均为-1），若是，则无冲突，更新I[x]的值即可，否则，说明两个“I x”之间没有任何一个“O x”，需要去查找在上个“I x”记录与当前“I x”记录之间是否有尚未被消费的‘？’（即以I[x]的值去set中查找下界），若无，则代表出现了错误，若有，则可以消费该‘？’（即将该‘？’从set中移除）。

上诉算法的实现如下（其实该版本实现得有问题，后面会讲到）：

#include <set>
#include <iostream>
#include <vector>
const int maxn = 500000 + 10;
using namespace std;

// 给定下界v后查找并消费？
bool process_unknown(set<int>& unkown, int v) {
    auto iter = unkown.lower_bound(v);
    if (iter == unkown.end()) {
        return true;
    }
    else {
        unkown.erase(iter);
        return false;
    }
}

int main(int argc, const char * argv[]) {
    int m = 0;
    string tmp;
    while (cin >> m) {
        getline(cin, tmp);
        vector<int> I(maxn, -1);
        vector<int> O(maxn, -1);
        set<int> unkown;
        bool wrong = false;
        string line;
        for (int i = 1; i <= m; i ++) {
            getline(cin, line);
            if (wrong) continue;
            if (line[0] == '?') {
                unkown.insert(i);
            }
            else {
                int x = stoi(line.substr(2));
                if (line[0] == 'I') {
                    if (I[x] <= O[x]) {
                        I[x] = i;
                    }
                    else {
                        wrong = process_unknown(unkown, I[x]);
                    }
                }
                else {
                    if (I[x] > O[x]) {
                        O[x] = i;
                    }
                    else {
                        wrong = process_unknown(unkown, O[x]);
                    }
                }
                if (wrong) {
                    cout << i << endl;
                }
            }
        }
        if (! wrong) {
            cout << -1 << endl;
        }
    }
    return 0;
}

上诉代码只过了50%的样例，看样子还有一种很极端的情况我们没有想到。

考虑问号可能的取值

我们突然想到了一种情况，如果’?’无值可取了怎么办，比如十万个不同的I跟着一个？再跟着十万个不同的O。在这种情况下，问号不管是I，还是O都会和现有的记录矛盾。

为了处理这种极端情况，我们需要记录下处理后的日志，并对处理后日志中剩下的问号进行处理，代码如下（在调这个版本的代码时发现了思路2中的一个bug，详见代码注释）：

// 忽略include
#define INF 1000000000
const int maxx = 100000;
const int maxn = maxx + 10;
using namespace std;

int main(int argc, const char * argv[]) {
    int m = 0;
    string tmp;
    while (cin >> m) {
        getline(cin, tmp);
        vector<int> I(maxn, -1);
        vector<int> O(maxn, -1);
        vector<pair<char, int> > record(1, {' ', 0});
        set<int> coupons;
        set<int> unkown;
        int lastPos = 0;
        bool wrong = false;
        string line;
        for (int i = 1; i <= m; i ++) {
            getline(cin, line);
            if (wrong) continue;
            if (line[0] == '?') {
                record.push_back({'?', 0});
                unkown.insert(i);
            }
            else {
                int x = stoi(line.substr(2));
                coupons.insert(x);
                record.push_back({line[0], x});
                if (line[0] == 'I') {
                    if (I[x] <= O[x]) {
                        I[x] = i;
                    }
                    else {
                        auto iter = unkown.lower_bound(I[x]);
                        if (iter == unkown.end()) {
                            wrong = true;
                        }
                        else {
                            unkown.erase(iter);
                            record[*iter] = {'O', x};
                            // 上一思路中的bug修复
                            I[x] = i;
                        }
                    }
                }
                else {
                    if (I[x] > O[x]) {
                        O[x] = i;
                    }
                    else {
                        auto iter = unkown.lower_bound(O[x]);
                        if (iter == unkown.end()) {
                            wrong = true;
                        }
                        else {
                            unkown.erase(iter);
                            record[*iter] = {'I', x};
                            // 上一思路中的bug修复
                            O[x] = i;
                        }
                    }
                }
                if (wrong) {
                    lastPos = i;
                }
            }
        }
        if (coupons.size() < maxx) {
            cout << (wrong ? lastPos : -1) << endl;
            continue;
        }
        //处理剩余的问号
        if (!wrong) {
            lastPos = m + 1;
        }
        set<int> haveI, allI, haveO;
        int lastO = lastPos, i = 1;
        while(i < lastPos) {
            while(i < lastPos && record[i].first != '?') {
                if(record[i].first == 'I') haveI.insert(record[i].second);
                else haveI.erase(record[i].second);
                i++;
            }
            i++;
            allI = haveI;
            haveO.clear();
            lastO = i;
            set<int> temHaveI = haveI;

            while(i < lastPos && record[i].first != '?') {
                if(record[i].first == 'I') {
                    allI.insert(record[i].second);
                    temHaveI.insert(record[i].second);
                }
                else {
                    temHaveI.erase(record[i].second);
                    if(haveI.find(record[i].second) != haveI.end() &&
                       haveO.find(record[i].second) == haveO.end()) {
                        haveO.insert(record[i].second);
                        lastO = i;
                    }
                }
                i++;
            }
            i++;

            if(allI.size() >= maxx && haveO.size() >= haveI.size()) {
                lastPos = lastO;
                break;
            }

            haveI = temHaveI;
        }
        cout << (lastPos == m + 1 ? -1 : lastPos) << endl;
    }
    return 0;
}

上诉代码终于AC了。

有没有可能我们考虑复杂了？

看样子是的，第三题的难度应该不至于那么难吧，感觉比第四题第五题难好多，而且貌似很多人没有考虑问号的取值也AC了。

调试的辛酸历程

刚写出思路三的时候，兴冲冲的提交上去还是只能过50%，各种样例都试过了还是找不到问题，于是就想到了万能的对拍大法，可是这道题有什么暴力版本吗？好像没有，那就只能简化问题了，考虑极端情况，如果优惠券的种类为1，那么记录中单数行只能是“I 1”或者问号，而双数行只能是“O 1”或者问号，代码如下，十分简单：

int main(int argc, const char * argv[]) {
    int m = 0;
    string tmp;
    while (cin >> m) {
        getline(cin, tmp);
        bool wrong = false;
        string line;
        for (int i = 1; i <= m; i ++) {
            getline(cin, line);
            if (wrong || line[0] == '?') continue;
            auto should_be = (i % 2 == 1 ? 'I' : 'O');
            // cout << should_be << " = " << line[0] << ": " << wrong << endl;
            wrong = (line[0] != should_be);
            if (wrong) cout << i << endl;
        }
        if (!wrong) {
            cout << -1 << endl;
        }
    }
    return 0;
}

将源程序中优惠券的种类设置为1，开始对拍，终于找到了问题。对于算法功底不强的我来说，对拍貌似是解决bug的最后一种手段了。

🏷

« 美团资格赛题解：1-2 美团资格赛题解：4 »