头歌 2022 春第一期 Greeker‘s party 13 周

第 1 关：疫情拐点 I

疫情已经持续数年。最近，A 国再次出现新一轮疫情高峰，B 团队正在尝试寻找拐点。该团队对拐点有如下定义：对于连续的三天，即第 j 天，j + 1 天，j + 2 天，报告的感染者数字 $p_i$ 满足 $p_{j+1}>p_j$ 且 $p_{j+1}>p_{j+2}$。如果存在拐点，则输出 "True"，否则输出 "False"。

直来直去，判断每一个 可能 是拐点的点（即下标范围在 1 ~ (m - 1)）是不是真正的拐点。核心代码如下：

bool flag = false;
for (int i = 1; i < m - 1; i++)
if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) {
flag = true;
break;
};
cout << (flag ? "True" : "False") << ' ';

时间复杂度是 $O(m)$，空间复杂度是 $O(m)$，完整代码见 GitHub

第 2 关：疫情拐点 II

该团队对拐点的定义方法进行了修改，现在调整为，存在三天（不需要连续）满足中间一天报告的感染者数字最大，前面的一天报告的感染者数字居中，最后一天报告的感染者数字最少，即存在 $i<j<k$ 满足 $p_j>p_i>p_k$，$i,j,k$ 不需要连续。

思考再三，我们可以遍历数组，过程中，保存当前选取的最优的 $p_i$ 和 $p_j$，最优的意思是 $p_j$ 和 $p_i$ 尽可能大，这样才更有利于找到一个小的 $p_k$。

具体地，我们以 nums[0] 为 $p_i$ 记为 numi，然后以从下标为 1 开始向后遍历的首个 大于 nums[0] 的数为 $p_j$ 记为 numj，这样就完成了 初始化。

int numi = nums[0], numj, idx = 1;
while (idx < m && nums[idx] <= nums[idx - 1]) idx++;
if (idx < m) numj = nums[idx];

于是我们继续遍历剩下的数组，当遍历到 nums[idx] 时，如果 nums[idx] > numj 的话，则我们遵循之前的原则尽可能让 numi 和 numj 大，所以同时更新 numi -> numj，numj -> nums[idx]；如果 nums[idx] < numi 的话，则我们神奇地发现已经找到了这样的三元组。

bool flag = false;
while (++idx < m) {
if (nums[idx] > numj) {
numi = numj;
numj = nums[idx];
} else if (nums[idx] < numi) {
flag = true;
break;
} else continue;
};
cout << (flag ? "True" : "False") << ' ';

时间复杂度是 $O(m)$，空间复杂度是 $O(m)$，完整代码见 GitHub

第 3 关：疫情拐点 III

该团队对拐点的定义方法进行了修改，现在调整为，存在三天（不需要连续）满足中间一天报告的感染者数字最大，前面的一天报告的感染者数字居中，最后一天报告的感染者数字最少，即存在 $i<j<k$ 满足 $p_j>p_i>p_k$，$i,j,k$ 不需要连续。

看上去很难的样子，我也只能想到相对来说较为复杂的做法，仅供参考吧。而且我实在是太懒了，所以我就用了 <vector> 和 <sort> 这两个 STL 库，各位小伙伴如果有好的解法欢迎与我交流鸭。

假设我们需要判断第 i 天是不是拐点，那么就要在第 0 ~ (i - 1) 天找到小于 nums[i] 的最大值记为 left，然后在第 (i + 1) ~ (m - 1) 天试图找到小于 left 的值记为 right，如果 right 存在就说明第 i 天是拐点。

一看数据范围 10^5 情况不妙，双循环 $O(m^2)$ 复杂度肯定超时，所以考虑用数组来维护，即对于第 i 天我们将维护一个左数组 pre 包含 0 ~ (i - 1) 的所有值，一个右数组 post 包含 (i + 1) ~ (m - 1) 的所有值，注意 pre 和 post 数组都是单调递增的，因此我们可以二分查找，在 $O(log(m))$ 复杂度找到 left 和 right。

在遍历第 i 天前，我们需要将 nums[i] 从 post 数组中删除，在遍历第 i 天后，我们需要将 nums[i] 插入 pre 数组中，注意，删除和插入操作都需要保证维护 pre 和 post 的有序性，因此需要先二分查找到删除和插入的位置再进行对应操作。

在 STL 的加持下，我们只需要用到 lower_bound 函数便能快速查找到大于等于某个值的第一个元素的位置。而 sort 能对整个数组进行排序，insert 则可以在数组某个位置插入一个新值。

int count = 0;
for (int i = 0; i < m; i++) {
post.erase(lower_bound(post.begin(), post.end(), nums[i])); // 从 post 数组删去 nums[i]
auto pre_iter = lower_bound(pre.begin(), pre.end(), nums[i]); // 找到第一个大于等于 nums[i] 的数，返回其迭代器
if (pre_iter != pre.begin()) {
--pre_iter; // 找到小于 nums[i] 的值最大的数
int left = *pre_iter;
auto post_iter = lower_bound(post.begin(), post.end(), left); // 在 post 数组尝试找到比 left 小的数 right
if (post_iter != post.end()) // 如果找到了这个数就代表这一天是拐点
++count;
};
pre.insert(lower_bound(pre.begin(), pre.end(), nums[i]), nums[i]);
};

时间复杂度是 $O(mlog(m))$，空间复杂度是 $O(m)$，完整代码见 GitHub

我觉得本次周赛的题目出的很不错，三道题的连贯性和区分度都是一流的，但不得不吐槽一下，禁用 STL 库是不合理的。俺知道此次比赛面向的同学主要是大一的，直接使用 STL 库可能会降低小朋友们对数据结构与算法的底层原理的掌握程度，但是在未来的学习与工作中，通常情况下，使用现成的轮子是比较好的做法。

我能理解禁用 STL 库的初衷，但我不赞成禁用 STL 库的做法，由于我刷题是为了保持写代码的手感，所以必要的时候还是会适当运用一些 STL 库里的东西。当然，我还是建议还在学《数据结构》课程的小朋友们，有空有兴趣的话，跟着课程进度自己实现一些基础的数据结构的模板吧，比如 vector ，stack 和 binaryTree 这种，毕竟 20 年疫情在家上网课的时候，我也都写过一遍呢。

最近在看《STL 源码分析》，坚持就是胜利！

好啦，以上就是第十二周周赛的全部内容，欢迎关注我的 GitHub 账号。

最后

以上就是虚心冬日最近收集整理的关于头歌 2022 春第一期 Greeker‘s party 13 周的全部内容，更多相关头歌内容请搜索靠谱客的其他文章。