题解：B3701 [语言月赛202301] 避雷针
$\textbf{Solution}$
$\textbf{F}_{\textbf{1}}$
观察 $n$ 的范围，由于 $1\le n\le10^6$，足以开下一个完整的数组，所以可以直接进行模拟。
对于每一个输入的 $a$，枚举 $\max\{a-2,1\}\sim\min\{a+2,n\}$，这样就不会越界了。可以开一个计数数组 $\rm cnt$，$\rm cnt_i$ 表示 $i$ 位置被劈中的次数。
最后遍历整个数组，统计即可。
时间复杂度 $O(n+m)$，空间复杂度 $O(n)$，可以通过本题。
$\textbf{F}_{\textbf{2}}$
考虑一种情况，当 $n$ 的范围非常大，以至于无法开一个数组记录时，应该如何解决呢？
首先，我们要使得时空复杂度与 $n$ 无关。对于每一个 $a$，影响的位置只有 $5$ 个，开一个数组记录的话很大一部分空间都被浪费了。
所以，我们只需要存储被劈过的位置，并且为了方便去重，并且使得时间复杂度较低，可以使用哈希表存储被劈过的位置。
$\textbf{Code}$
$\textbf{F}_{\textbf{1}}$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| #include <iostream>
const int MAX = 1e6 + 10;
int n, m, ans, t[MAX];
int main() {
std::cin >> n >> m;
for (int i = 0, a; i < m; ++i) {
std::cin >> a;
for (int j = std::max(a - 2, 1); j <= std::min(a + 2, n); ++j) ++t[j];
}
for (int i = 1; i <= n; ++i) ans += t[i] >= 1;
std::cout << ans << std::endl;
return 0;
}
|
$\textbf{F}_{\textbf{2}}$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| #include <iostream>
#include <unordered_set>
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
int n, m;
std::unordered_set<int> set;
int main() {
std::cin.tie(0)->sync_with_stdio(0);
std::cin >> n >> m;
for (int a; m; --m) {
std::cin >> a;
for (int i = max(1, a - 2); i <= min(a + 2, n); ++i) set.insert(i);
}
std::cout << set.size() << std::endl;
return 0;
}
|