B3692题解

· · 题解

分析

这题是一道模拟题，只需按照题意模拟并加上适当的算法即可。

首先，对于每支队伍，我们用一个结构体来存储信息。每支队伍的信息包括：这支队伍的名称，编号（有提交记录先后决定），罚时，通过题目数以及每道题的通过或不通过情况。

由于滚榜是不断更新的，滚榜内每支队伍的信息也是回不断改变的，所以，我们用堆来存储滚榜（也就是优先队列）。使用堆的好处是：每次在堆里添加一个队伍，那么堆内队伍的排列就会发生改变，符合滚榜的变化。

为了方便起见，我们重载小于号，根据题意，由通过题目数、罚时、编号来判断两支队伍的大小关系。那么在进行堆的插入操作时，也会按照这样的大小关系排序。

做完准备工作后，开始模拟过程。

首先对于每条提交记录，我们要判断提交队伍是否出现（用键值对存储）。如果没出现，那么添加这支队伍，并将队伍的信息初始化；如果出现过，则获取这支队伍的编号，以便得到这支队伍的信息。

如果该队伍通过了此题，则无需进行下面的操作；否则，继续进行判断。

如果该题的提交状态为不通过，则将改题目的提交数加一；否则，计算该队伍的罚时，并标记该题为通过。

需要注意的一点是，如果这条提交记录是在封榜后出现的，则进行特殊标记，并记录该题的罚时（不能更新该队伍的总罚时），在滚榜时再计算总罚时。

处理完所有提交记录后，将每支队伍加入堆中，并进行滚榜操作。

我们取出并弹出队首，并输出队首队伍的名称，计算每题在封榜后的罚时，若队首队伍的罚时加上该题的罚时后，滚榜会发生变化，那么重新加入堆中，并结束该操作。

Code

#include <bits/stdc++.h>
using namespace std;

struct dui {
    int fa;
    string name;
    int id;
    int guo;
    int to[40];
    int bu[40];
    bool operator <(const dui &l) const {
        if (guo != l.guo)
            return guo > l.guo;
        else if (fa != l.fa)
            return fa < l.fa;
        else
            return id < l.id;
    }
} s[1005];
int o;
map<string, int>q;
priority_queue<dui>pai;

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 1; i <= k; i++) {
        string a, b, c, d;
        cin >> a >> b >> c;
        getline(cin, d);
        int x = 0, yy = 0, zz = 0;
        int p = 0;
        for (; p < a.size(); p++) {
            if (a[p] == ':')
                break;
            x = x * 10 + (a[p] - '0');
        }
        p++;
        for (; p < a.size(); p++) {
            if (a[p] == ':')
                break;
            yy = yy * 10 + (a[p] - '0');
        }
        p++;
        for (; p < a.size(); p++) {
            if (a[p] == ':')
                break;
            zz = zz * 10 + (a[p] - '0');
        }
        if (!q[c]) {
            q[c] = ++o;
            s[o].name = c;
            s[o].id = o;
            s[o].guo = 0;
            s[o].fa = 0;
            memset(s[o].to, 0, sizeof(s[o].to));
            memset(s[o].bu, 0, sizeof(s[o].bu));
        }
        int iid = q[c];
        int ti = b[0] - 'A' + 1;
        int shi = x * 60 + yy;//时间
        if (s[iid].to[ti])
            continue;
        if (d == " Accepted") {
            s[iid].to[ti] = 1;
            if (shi > 240 || (shi == 240 && zz)) {//特判
                s[iid].to[ti] = 2 + shi + 20 * s[iid].bu[ti];
            } else {
                s[iid].fa += shi + 20 * s[iid].bu[ti];
                s[iid].guo++;
            }
        } else
            s[iid].bu[ti]++;
    }
    for (int i = 1; i <= o; i++) {
        pai.push(s[i]);
    }
    while (pai.size() > 1) {
        dui x = pai.top();
        pai.pop();
        cout << x.name << endl;
        dui y = pai.top();
        pai.pop();
        for (int i = 1; i <= n; i++) {
            if (x.to[i] > 1) {
                x.fa += x.to[i] - 2;
                x.guo++;
                x.to[i] = 1;
                if (x < y) {
                    pai.push(x);
                    break;
                }
            }
        }
        pai.push(y);
    }
    cout << pai.top().name;
}