P3709. 信号塔关联激活

解题思路

示例解析及题目总分析

考虑示例二的过程，可以看到最后被启动的发动机是 4 和 5。

首先我们可以比较快速地定位出这是一个 BFS 问题。 因为上一时刻启动的发动机，会使得其相邻的其他未启动发动机在下一个时刻启动。 这有点类似于 病毒感染 或者 波纹传播 等模型。

主要要解决两个问题：

1. 这是一个 1 维环型数组，和我们经常遇到的二维网格模型有所不同。 2. 本题还存在 时间先后 的概念，某些发动机在中间的某些时刻会被 手动启动（而不都是在最开始被启动）。

把上述两个问题处理好，加以我们常用的 BFS 解题套路，本题其实不算难题。

---

处理一维环型数组

常规的二维网格 DFS/BFS，在考虑近邻位置的时候，我们是取 上下左右 四个方向。 对于一维数组某一个元素的近邻位置，我们只需要考虑 左右 两个方向。

特别地，由于需要处理 环型数组，我们在位置 0 和位置 N-1 需要进行额外判断。 可以构建函数 get_neighbor() 进行分类讨论，来获得元素 x 的两个近邻位置，即：

或者使用 取余 的写法，即：

---

处理延时入队问题

另一个更加重要的问题是 延时处理 的问题。 由于同一个时刻启动的发动机可能不止一台，我们首先使用 哈希表 来储存所有手动启动的发动机的信息。

哈希表 table 中储存了所有手动启动的发动机信息。 其中 key 为若干的启动时刻 T，value 为在同一个 T 中启动的若干发动机 P 构成的列表。

例如对于例子：

构建的哈希表为：

我们知道，在 BFS 过程中的元素出队意味着我们要考虑其近邻元素的情况。 如果是不考虑延时入队的普通情况，我们会这样来完成 BFS 过程：

特别注意，total 表示的是发动机的 启动总数量。 在单层搜索下（同一个时刻的搜索），队列 q 中的所有元素都是在当前时刻要启动的发动机编号。 所以在当前时刻，total 增加的量为 qSize = len(q)。

为了找到 最后一次启动 的那些机器，我们可以多设置一个条件用来判断。 一旦发现 total 增加后数量为 N，说明在这个时刻中队列 q 中的所有元素，就是最后启动的发动机编号，也就是答案。因此我们可以看到代码中存在：

其中 ans 就是最终要输出的答案。

---

现在我们把 延时入队 的事情考虑进来。 在 BFS 过程中，我们可以设置一个变量 cur_time，来表示当前进行到的时刻。 在进行到某一个时刻的时候，如果发现 cur_time 位于 table 中，意味着存在若干发动机是在这个时刻被 手动启动 的。这些发动机需要被加入到队列 q 中。即：

这部分代码必须加在 更新 `total` 之前。 另外，每次 while 循环结束后，cur_time 还需要递增 1，表示整体的时刻增加。因此 BFS 过程的整体代码为：

复杂度分析 设信号塔个数为 N，手动激活信息条数为 E。读入并构建哈希表 table 为 O(E)，取所有手动激活时刻的最小值也是 O(E)。BFS 主体中，check_list 保证每个信号塔至多入队一次，出队时只考察环上左右两个邻居，出入队的总代价为 O(N)；每条手动激活信息也只在对应时刻被处理一次，共 O(E)。需要注意外层 while 是按时刻逐轮推进的（cur_time 从最小手动激活时刻开始每轮加一），若手动激活时刻之间有空档，中间轮次只做常数工作，因此循环轮数取决于最晚有效激活时刻与 N 的量级。最后对最晚激活的塔编号排序，设其数量为 K（K 不超过 N），代价 O(K log K)。综合起来时间复杂度为 O(N + E + K log K) 再加上时刻推进的轮数；空间上 check_list 为 O(N)，哈希表为 O(E)，队列至多 O(N)，即 O(N + E)。