C. 左右房屋 详细题解

题目核心理解

村庄里有 $n$ 栋房屋，用一串仅含 $0/1$ 的字符串表示居民意愿：

• $a_j=0$：第 $j$ 户想住在道路左侧
• $a_j=1$：第 $j$ 户想住在道路右侧

道路可以建在第 $i$ 栋房屋之后（$i$ 可取 $0$ 到 $n$）：

• 左边：$1\sim i$ 号房屋
• 右边：$i+1\sim n$ 号房屋

修路要求：

1. 左侧房屋中，想要住左边（$0$）的数量 ≥ 想要住右边（$1$）的数量
2. 右侧房屋中，想要住右边（$1$）的数量 ≥ 想要住左边（$0$）的数量

在所有满足条件的 $i$ 中，选出最靠近 $\dfrac{n}{2}$ 的位置； 若距离相同，选更小的 $i$。

---

核心思路

1. 关键转化

原题要求“每边至少一半人满意”，向上取整后等价于：

• 左侧：$0$ 的个数 $\ge$ $1$ 的个数
• 右侧：$1$ 的个数 $\ge$ $0$ 的个数

2. 快速统计

使用前缀和数组预处理 $1$ 的数量，实现 $O(1)$ 查询任意区间：

• 前 $i$ 个里 $1$ 的数量：$\text{pre}[i]$
• 前 $i$ 个里 $0$ 的数量：$i - \text{pre}[i]$
• 右侧 $i+1\sim n$ 里 $1$ 的数量：$\text{pre}[n] - \text{pre}[i]$

3. 最优位置判断

为避免浮点数精度问题，用 $|n - 2\cdot i|$ 代替 $|\dfrac{n}{2} - i|$ 比较距离，结果完全等价。

• 该值越小，说明 $i$ 越靠近中间
• 若值相同，保留较小的 $i$

---

算法流程

1. 预处理前缀和数组 $\text{pre}$，记录前 $i$ 位中 $1$ 的个数。
2. 枚举所有可能的修路位置 $i\in[0,n]$。
3. 对每个 $i$ 统计左侧 $0$、左侧 $1$、右侧 $1$、右侧 $0$。
4. 判断是否满足：左侧 $0\ge1$ 且 右侧 $1\ge0$。
5. 在合法位置中，选出 $|n-2i|$ 最小的 $i$；并列时选更小的 $i$。
6. 输出最优的 $i$。

---

公式与复杂度分析

合法性条件：

$$(i - \text{pre}[i])\;\ge\;\text{pre}[i]$$ $$(\text{pre}[n] - \text{pre}[i])\;\ge\;(n-i-(\text{pre}[n]-\text{pre}[i])) $$

最优比较指标：

$$\textit{score} = |n - 2\cdot i|$$

复杂度

• 预处理前缀和：$O(n)$
• 枚举所有位置：$O(n)$ 总时间复杂度：$O(n)$。

可轻松处理 $n\le 3\times 10^5$、多组数据总长度不超过 $3\times 10^5$ 的范围。