题解十一：B3692 [语言月赛202212] 打 ACM 最快乐的就是滚榜读队名了(Easy Version)

· · 题解

看了一下题解区，几乎所有题解都使用了诸如 priority_queue 和 unordered_map 之类的东西，那我就来发一篇不借助任何 STL 的题解。

题目传送门：B3692 [语言月赛202212] 打 ACM 最快乐的就是滚榜读队名了(Easy Version)。

这题目名怎么和题面一样长的离谱。

思路

从标签中，我们不难看出这是一道模拟。

既然是模拟还有什么好讲的，直接看代码。

这里先说一下本人采的几个坑：

  1. 注意滚榜过程中，每一次只公布队伍一道“待判题”，直到下一次遇见这只队伍才会再公布下一道；
  2. 分钟数超过 240 要封榜，分钟数等于 240 但是有秒数也要封榜；
  3. 通过越多成绩越好，时间却是越短成绩越好；
  4. 如果评测状态使用 getline(); 读入，会把评测状态前的一个空格读进来；
  5. 下标！下标！打了半个小时后就忘了自己数组下标是从哪开始的了……

其他内容全写在代码注释里了，有一点多。

代码

// 421ms / 1.04MB / C++17 O2
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,k;//如题目
ll fz,tot,id,tm1;//分钟数，提交队伍数，队伍编号，题目编号（整数）
string mz,sj,zt;//队伍名字，提交时间，评测状态
char tm2;//题目编号（字符）
bool flag;//是否封榜
struct team{
    ll sj[25],zsj,zsj2,ztg,ztg2,id;
    //依次：每道题的罚时，总罚时，封榜后的总罚时，总通过数，封榜后的总通过数，队伍编号
    bool tg[25],tg2[25];//是否通过每道题，封榜后是否通过每道题
    string mz;//队伍名字
}t[1010];
bool cmp(team x,team y){//成绩差的排在前面
    if(x.ztg!=y.ztg) return x.ztg<y.ztg;//通过数越少越差
    if(x.zsj!=y.zsj) return x.zsj>y.zsj;//总罚时越长越差（思路 3）
    return x.id>y.id;//编号越靠后越差
}//cmp 不仅 sort 时要用，到滚榜时也要用
int main(){
    cin>>n>>m>>k;
    while(k--){
        cin>>sj>>tm2>>mz;
        getline(cin, zt);
        tm1=tm2-'A';//把题目编号从字符变为数字。注意这样下标从 0 开始（思路 5）
        fz=(sj[0]-'0')*60+(sj[2]-'0')*10+sj[3]-'0';//分钟数
        //以下判断是否封榜
        if((fz>240 or (fz==240 and sj[5]-'0'+sj[6]-'0'>0)) and flag==false){
            //sj[5] 和 sj[6] 对应时间的秒数（思路 2）。已经封过就不重复了
            flag=true;//开始封榜
            for(ll i=1;i<=tot;i++){//遍历所有队伍，把封榜后的通过数和罚时先更新为封榜前的
                t[i].ztg2=t[i].ztg;
                t[i].zsj2=t[i].zsj;
            }//其实有点多余。可以在下面每一次处理时就同步把封榜后的数更新
        }
        //以下判断这只队伍是否出现过
        id=0;//队伍编号
        for(ll i=1;i<=tot;i++)//查询已有队伍
            if(t[i].mz==mz){//看是不是同一支
                id=i;
                break;
            }
        if(id==0){//如果没查到，说明是新出现的
            t[++tot].mz=mz;//更新
            id=t[tot].id=tot;
        }
        //以下正式对这次提交进行操作
        if(t[id].tg[tm1]==true) continue;//如果这个团队已经通过这道题，直接不管
        if(zt==" Accepted"){//注意空格（思路 4）
            t[id].tg[tm1]=true;//这道题通过
            t[id].sj[tm1]+=fz;//时间更新
            if(flag){//如果已经封榜
                t[id].ztg2++;//封榜后通过数增加
                t[id].zsj2+=t[id].sj[tm1];//封榜后总罚时增加
                t[id].tg2[tm1]=true;//封榜后这道题通过
            }else{//否则
                t[id].ztg++;//封榜前通过数增加
                t[id].zsj+=t[id].sj[tm1];//封榜前总罚时增加
            }
        }else t[id].sj[tm1]+=20;//如果评测状态为不通过，这道题增加罚时
    }
    sort(t+1,t+tot+1,cmp);//排序
    for(ll i=1;i<=tot;){//从差到好输出
        cout<<t[i].mz<<'\n';
        if(i<tot and t[i].ztg<t[i].ztg2){//第一，不是最后一个；第二，封榜前后通过数不一致
            for(ll j=0;j<n;j++)//遍历每一道题
                if(t[i].tg2[j]){//找到最靠前的封榜后通过的题
                    t[i].tg2[j]=false;//删掉标记防止重复
                    t[i].zsj+=t[i].sj[j];//封榜前总罚时增加
                    t[i].ztg++;//封榜前总通过增加
                    break;//找到一个就跳出（思路 1）
                }
            for(ll l=i,j=i+1;j<=tot;l++,j++)//往后更新它的位置
                if(cmp(t[j],t[l]))//如果后面的队伍可以放在它前面
                    swap(t[j],t[l]);//就把它往后放（交换）
                else break;//找不到了就跳出
        }else i++;//如果不更新位置，就找下一位
        //（如果更新位置了，那么当前位置就是从下一位交换过来的）
    }return 0;
}//不要抄袭！！！！！

吐槽

样例这么水根本查不出错啊。