自动搬运

查看原文

来自洛谷，原作者为

	chen_zhe Aya 敲可爱的~

搬运于2025-08-24 22:43:27，当前版本为作者最后更新于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);
}

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

1. 可以使用一个数组去存储当前这个队伍已经滚榜到哪一题了，这个可以轻松使用 unordered_map 完成。顺带一提，我之前开了个 unordered_map <string,vector <Event> :: iterator> itmap;，但是会 RE，改成寻常的下标访问即可，原因不明。

2. 滚榜阶段每次从优先队列中取出两个元素，一个是 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。写起来总的来说还是有点痛苦。