题解 P8890

chen_zhe · 2022-12-12 17:23:24 · 题解

~~不会有人写大模拟题解吧，不会吧不会吧。~~

作为语言月赛的最后一题，这个题应当说是有一定难度的，考察了模拟的基本功，也考察了如何使用优先队列去优化模拟过程，代码中也有一定的细节，考察基本的码力。

首先不难想到的是，将队伍用一个结构体打包起来，存下这个队伍的 AC 题数，罚时，提交编号，队伍名。此外，我们还需要存储的是这个队伍每个题提交了多少次（数组 f[i]，特别的，代码中规定如果 f[i]==K+1 为过题），以及这个队伍有哪些提交需要被滚榜（vector <Event> r）。此外，由于最后肯定是要对队伍进行排序的，因此这里按照 AC 数、罚时和提交编号进行了重载运算符。

struct team {
    int ac,ftime,id;
    int f[26];
    string tname;
    vector <Event> r;
    bool operator < (const team &rhs) const {
        if (ac!=rhs.ac)
            return ac<rhs.ac;
        else if (ftime!=rhs.ftime)
            return ftime>rhs.ftime;
        else
            return id>rhs.id;
    }
    bool operator > (const team &rhs) const {
        if (ac!=rhs.ac)
            return ac>rhs.ac;
        else if (ftime!=rhs.ftime)
            return ftime<rhs.ftime;
        else
            return id<rhs.id;
    }
};

由于队伍的名称是字符串，因此我们用一个 unordered_map 存储队名。接着要设计每一发提交的结构体 Event。这里存放的是提交时间，提交状态，提交编号，提交题号和队伍名称。

struct Event {
    int time,status,id;
    char p;
    string name;
};

我们首先读入，将每一发提交存在一个结构体数组中。接着我们处理前四个小时的情况，方便我们到时候滚榜。这里需要介绍一个让代码写起来很方便的语法糖：结构化绑定。尽管这应该是 c++17 才引入的特性，由于 gcc 的支持，其可以在 NOI 等赛事下使用（gcc 9.3,-std=c++14）。

其使用方式中，有一种如下：

struct Foo {
    int a,b;
}t;

auto [a,b]=t;

这样的代码等价于 a=t.a,b=t.b;。此外，还可以让 a,b 成为 t.a 和 t.b 的引用，只需写成形如 auto &[a,b]=t 即可。这样就可以写出计算前四个小时的成绩的代码：

for (auto [time,ok,id,p,name] : e) {
    if (time<=240*60) {//前四个小时
        if (!t.count(name)) {//如果没有这个队伍再新建。
            t[name].tname=name;
            t[name].id=id;
        }
        if (ok==1) {//这是一条 AC 记录。
            auto &[ac,ftime,id,f,tname,r]=t[name];
            if (f[p]==K+1)//如果已经 AC 则不更新
                continue;
            ftime+=f[p]*20*60+time/60*60;
            ac++;
            f[p]=K+1;
        }
        else {
            auto &[ac,ftime,id,f,tname,r]=t[name];
            if (f[p]==K+1)
                continue;
            f[p]++;
        }
    } else {//最后一个小时
        if (t.count(name)==0) {//滚榜期间也可以有新队伍
            t[name].tname=name;
            t[name].id=id;
        }
        t[name].r.push_back({time,ok,id,p,name});
        //将其插入存放有哪些提交需要被滚榜的 vector
    }
}

这里需要指出的是，对于 map 和 unordered_map，直接使用下标去访问的话，哪怕如果没有对应的下标的元素，也会自动给你新建一个元素出来。比较好的方式是使用 count() 这个成员函数去看是否有对应元素。

接着由于滚榜的时候，是从 A 一直到 Z 题去滚榜的，因此需要对 r 这个 vector 中，根据 id 作为大小进行排序，接着将这些队伍统统塞入优先队列中。为了让代码好看，排序的 cmp 直接使用 lambda 表达式完成。此外，由于无法对 unordered_map 排序，这里将其插入一个 vector 中。

for (auto [fir,sec]:t)
    t2.push_back(sec);
stable_sort(t2.begin(),t2.end());
for (auto &v:t2) {
    auto &t=v.r;
    sort(t.begin(),t.end(),[](auto a,auto b) {
        return a.p<b.p;
    });
    q.push(v);
}

接着就进入了滚榜的流程。滚榜过程中，有两个注意点：

可以使用一个数组去存储当前这个队伍已经滚榜到哪一题了，这个可以轻松使用 unordered_map 完成。顺带一提，我之前开了个 unordered_map <string,vector <Event> :: iterator> itmap;，但是会 RE，改成寻常的下标访问即可，原因不明。
滚榜阶段每次从优先队列中取出两个元素，一个是 st1 表示当前的队伍，一个是 st2 表示上一个队伍。在拿 st2 前如果优先队列已经空了其实就说明是排名第一。给 st1 滚了榜后要判断一下是否满足 st1>st2，如果成立就插入优先队列进行后续滚榜。参考代码：

while (!q.empty()) {
    auto st1=q.top();
    auto &[ac,ftime,id,f,tname,r]=st1;
    q.pop();
    cout << tname << " ";
    cout << "\n";
    if (q.empty())
        break;
    if (r.empty())// 没有要滚榜的提交
        continue;
    auto st2=q.top();
    size_t it=(itmap.count(tname)?itmap.at(tname):0);
    for (;it<r.size() && st1<st2;it++) {
        auto [time,status,tid,p,name]=r[it];
        if (!t.count(name)) {
            t[name].tname=name;
            t[name].id=tid;
        }
        if (f[p]==K+1)
            continue;
        if (status==0)
            f[p]++;
        else {
            ac++;
            ftime+=f[p]*20*60+time/60*60;
            f[p]=K+1;
        }
    }
    itmap[tname]=--it;
    if (st1>st2)
        q.push(st1);
}

这样我们就完成了本题。实际上代码细想一下其实是不难的，但是我当时半小时写完后挂了一些细节，调了一段时间，然后因为 f 数组开了 unordered_map 造成了偏大的常数 TLE。写起来总的来说还是有点痛苦。