202301F 避雷针 题解

· · 题解

[语言月赛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 并输出即可。

视频题解

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