自动搬运

查看原文

来自洛谷，原作者为

	Maxmilite **

搬运于2025-08-24 21:14:30，当前版本为作者最后更新于2023-01-05 21:08:49，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

[语言月赛202301] 避雷针 题解

Source & Knowledge

2023 年 1 月语言月赛，由洛谷网校入门计划/基础计划提供。

文字题解

题目大意

给定 $n, m$ 和一串序列 $a _ 1, \cdots, a _ m$。

对于第 $i$ 个元素，其影响了 $a _ i - 2$（如果存在）、$a _ i - 1$（如果存在）、$a _ i$、$a _ i + 1$（如果存在）、$a _ i + 2$（如果存在）这些位置。

需要计算最后 $n$ 个位置中有几个位置被影响到。

解析

注意到 $1 \leq n,m \leq 10 ^ 6$，所以我们可以直接建立长度为 $10 ^ 6$ 的数组 $f$，并全体初始化为 $0$。

对 $m$ 个元素，如果某一元素影响了 $i$ 号位置，我们便将 $f _ i$ 标记为 $1$。

需要注意的是，题目仅保证 $1 \leq a _ i \leq n$，因此直接访问 $f$ 数组的 $a _ i - 2$ 等下标对应的位置可能会导致越界访问。

这里一个比较取巧的方法是，在遍历 $a _ i - 2 \sim a _ i + 2$ 时，我们将遍历范围直接使用 max 和 min 函数限定到 $[1, n]$ 内。核心代码如下：

for (int i = 1, x; i <= m; ++i) {
	scanf("%d", &x);
	for (int j = max(1, x - 2); j <= min(n, x + 2); ++j)
		f[j] = 1;
}

最后统计 $f$ 数组中有几个 $1$ 并输出即可。

视频题解

完整代码请在视频中查看。