自动搬运

查看原文

来自洛谷，原作者为

	yiLIUyi 不屈的江油人民终会迎来光明|看主页：F12删除“display: none;”|互关条件luogu.com.cn/paste/x54efpmj 满足可私信|准九年级|山东|可以加微信/qq聊天

搬运于2025-08-24 21:14:26，当前版本为作者最后更新于2025-08-18 17:06:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

看了一下题解区，几乎所有题解都使用了诸如 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;
}//不要抄袭！！！！！

吐槽

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