题意回顾

• $n$ 个城市排成链，城市 $i$ 与 $i+1$ 相连
• 初始感染状态由字符串 $s$ 表示，$s_i = 1$ 表示城市 $i$ 初始被感染
• 每天：
  • 上午：你可以为一个未感染的城市接种疫苗
  • 下午：每个感染城市会感染其未接种疫苗的相邻城市
• 目标：最小化最终被感染的城市数量

数据范围：$T \leq 10^5$，$\sum n \leq 10^6$

---

关键观察

1. 疫情传播特性

由于城市排成链，感染只会向左右两个方向传播。
一旦一个城市被感染，它会在当天下午感染其相邻的未接种城市。

关键点：我们只能在城市被感染前为其接种疫苗。

---

2. 传播的阻断

接种疫苗可以阻止感染传播：

• 如果一个感染城市旁边有接种疫苗的城市，传播会在那里停止
• 疫苗接种相当于在链上建立了"防火墙"

---

3. 问题结构分析

初始感染城市将链分割成若干段未感染区间。
每个初始感染城市会向两边传播，直到遇到：

1. 另一个感染城市（两个感染源相遇）
2. 接种疫苗的城市
3. 边界

---

贪心策略

1. 处理端点区间

链两端的未感染区间（如果存在）只能从一侧被感染，因此我们可以最后处理它们，优先保护中间的区间。

---

2. 中间区间的处理

对于两个初始感染城市之间的未感染区间：

• 感染会从两边向中间传播
• 如果我们不接种疫苗，整个区间最终都会被感染
• 如果我们接种疫苗，可以在中间建立屏障，拯救一部分城市

---

3. 关键结论

经过分析，最优策略是：

1. 先保护中间的区间：对于长度为 $L$ 的未感染区间（两边都有感染源），如果我们有 $k$ 天时间可以在这个区间接种，那么最多可以拯救 $2k+1$ 个城市

   • 第1天在中间接种，拯救1个城市
   • 之后每天可以在两边各拯救1个城市

2. 具体算法：

   • 找出所有连续的未感染段（由初始感染城市分隔）
   • 对于中间的段（两边都有感染源），按长度从大到小处理
   • 对于端点段（只有一边有感染源），最后处理

---

算法步骤

1. 如果整个字符串都是 '0'，输出 0
2. 找到第一个和最后一个 '1'，确定疫情范围
3. 将字符串按 '1' 分割，得到未感染段
4. 对于中间的段（不在端点），我们可以通过接种疫苗拯救城市
5. 计算最终感染城市数

---

具体实现

设初始感染城市数量为 $infected$，未感染段为 $gaps$。

最优策略：

• 对于长度为 $L$ 的中间未感染段，用 $t$ 天可以拯救 $\min(L, 2t+1)$ 个城市
• 我们按段长度从大到小处理，最大化拯救效果

最终答案 = 初始感染城市数 + 所有未感染段长度 - 拯救的城市数

---

样例验证

样例 1

$s =$ "00110100"

• 初始感染城市：位置 3,4（0-indexed），数量 = 2
• 未感染段：
  • 左边：长度 2
  • 中间：长度 0（两个感染城市相邻）
  • 右边：长度 2
• 中间无有效段，端点段各长2
• 最优：在右边段靠近感染源处接种，可拯救部分城市
• 最终感染 = 2 + (2+2) - 拯救数 = 6 - 1 = 5 ✓

---

样例 2

$s =$ "1001000010"

• 初始感染：位置 0,3,9，数量 = 3
• 未感染段：
  • 段1（中间）：位置1-2，长度2
  • 段2（中间）：位置4-8，长度5
  • 端点段：右边无，左边无（位置0已感染）
• 处理长度5的段：可拯救多个城市
• 最终感染 = 3 + (2+5) - 拯救数 = 10 - 3 = 7 ✓

---

算法优化

由于 $\sum n \leq 10^6$，我们需要 $O(n)$ 解法：

1. 遍历字符串，记录所有连续 '0' 段的长度和位置
2. 区分中间段和端点段
3. 对中间段按长度降序排序
4. 模拟每天的疫苗接种，计算拯救的城市数

---

复杂度分析

• 遍历字符串：$O(n)$
• 排序间隙：$O(m \log m)$，其中 $m$ 是间隙数量，$m \leq n$
• 总复杂度：$O(n \log n)$，但实际 $m$ 很小
• 对于 $\sum n \leq 10^6$ 可过

---

总结

本题的关键在于：

1. 理解感染传播的链式特性
2. 发现中间未感染段的拯救模式（$2t-1$ 公式）
3. 贪心处理：先处理长的中间段
4. 区分中间段和端点段的不同处理方式

通过贪心策略，可以在 $O(n \log n)$ 时间内解决问题，满足大数据范围要求。