自动搬运

查看原文

来自洛谷，原作者为

	Cocoly1990 成事不说 遂事不谏 既往不咎

搬运于2025-08-24 22:35:50，当前版本为作者最后更新于2022-02-03 21:34:20，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

官方题解。

A

考虑顺序处理每一条记录，如何处理两个约束条件是本题的核心。

首先对于 $t\leq1$ 可以在读入的时候直接判断处理，忽略即可。

cin >> x >> t;
if(t <= 1) continue;

那么如何判断这首歌之前是否被累加过呢？一种做法是记录下所有的记录，扫描之前的判断是否累计过。

cin >> x0 >> t0;
if(t0 <= 1) continue;
bool f = 1;
for(int j = 1; j <= cnt; j ++){
	if(x[j] == x0) f = 0;
}
if(f) {
	ans += t0; x[++ cnt] = x0; t[cnt] = t0;
}

容易发现上述做法的时间复杂度是 $\mathcal{O}\left(n^2\right)$ 的，可以通过 $40\%$ 的数据。那么我们何不开一个桶，记录某首歌是否又被听过？

cin >> x >> t;
if(t <= 1) continue;
if(vis[i]) continue;
else {
	ans += t;vis[x] = 1;
}

上述做法的时间复杂度是 $\mathcal{O}\left(n\right)$ 的，可以通过 $100\%$ 的数据。