A. 前往 Pénjamo 的巴士 详细题解

1. 问题理解

• 有 $n$ 个家庭，第 $i$ 个家庭有 $a_i$ 名成员。
• 巴士有 $r$ 排，每排 $2$ 个座位。
• 一个人是快乐的，如果：
  1. 同一排有另一名同家庭成员，或者
  2. 他独自坐一排（旁边的座位空着）。
• 目标：安排所有人坐下，最大化快乐人数。

---

2. 关键观察

观察 1：同家庭成员坐在一起是最优的

• 如果两个同家庭的人坐在同一排，两人都快乐，且只占用 $2$ 个座位。
• 如果把他们分开，每人只能快乐一个（如果单独坐一排），但占用 $2$ 个座位。
• 因此，优先让同家庭的人成对坐在一起。

观察 2：每对同家庭的人贡献 $2$ 个快乐人数

• 对于家庭 $i$，可以形成 $\lfloor a_i / 2 \rfloor$ 对，每对占用 $1$ 排，贡献 $2$ 个快乐人数。
• 这些对是必定快乐的，且是最优的。

观察 3：剩余未配对的人的处理

• 每个家庭可能剩余 $a_i \% 2$ 个人（$0$ 或 $1$）。
• 这些未配对的人需要坐在剩余的排中。
• 如果一个人独自坐一排，他快乐（条件 2）。
• 如果两个人（不同家庭）被迫坐同一排，两人都不快乐（不满足条件 1，也不满足条件 2）。

---

3. 算法步骤

1. 初始化：

   • happy = 0：快乐人数
   • leftalone = 0：未配对的人数（即所有 $a_i \% 2$ 之和）
   • r：剩余排数

2. 处理成对：

   • 对每个家庭 $i$：
     • happy += (a[i] / 2) * 2
     • r -= a[i] / 2（每对占用一排）
     • leftalone += a[i] % 2

3. 处理未配对的人：

   • 如果 leftalone <= r：
     • 每个未配对的人都可以独自坐一排 → 全部快乐
     • happy += leftalone
   • 否则（leftalone > r）：
     • 只有 $r$ 排可以给未配对的人单独坐 → $r$ 个人快乐
     • 剩下的 leftalone - r 个人必须与其他人共享一排 → 不快乐
     • 注意：当两个人共享一排时，他们各自失去快乐，但原本如果单独坐他们会快乐，现在不快乐，所以总快乐人数减少 $2 \times (leftalone - r)$？
     • 更简单的公式：此时快乐人数 = happy + r * 2 - leftalone
     • 推导：
       • 总共有 $r$ 排可以容纳未配对的人，每排最多 $2$ 人
       • 如果 $r$ 排全部坐满，最多容纳 $2r$ 人
       • 但只有 leftalone 个未配对的人需要坐
       • 如果 leftalone > r，则至少 leftalone - r 个人必须两人一排
       • 每两个共享一排的人，原本如果各自单独坐会贡献 $2$ 快乐，现在贡献 $0$ → 损失 $2$
       • 所以总快乐 = 初始快乐 + 单独坐的快乐 - 损失
       • 实际上，最终公式为 happy + r * 2 - leftalone

---

4. 公式推导

设：

• pairs = 总成对数 = $\sum \lfloor a_i / 2 \rfloor$
• left = 未配对人数 = $\sum (a_i \% 2)$
• 初始快乐 = $2 \times \text{pairs}$
• 剩余排数 $r' = r - \text{pairs}$

情况 1：left <= r'

• 所有未配对的人都可以单独坐一排
• 总快乐 = $2 \times \text{pairs} + \text{left}$

情况 2：left > r'

• 只有 $r'$ 排可以单独坐，即 $r'$ 个人快乐
• 剩下 left - r' 个人必须两两共享一排（或与其他人共享）
• 每两个共享一排的人，原本如果单独坐会贡献 $2$ 快乐，现在贡献 $0$ → 损失 $2$
• 总快乐 = $2 \times \text{pairs} + r' - 2 \times (\text{left} - r')$？不对，再仔细算：

更简单的推导：

• 总人数 = $2 \times \text{pairs} + \text{left}$
• 剩余排数 $r'$ 可以容纳最多 $2r'$ 人
• 但只有 left 个未配对的人需要安排
• 在 $r'$ 排中：
  • 每排如果坐 $2$ 人，则 $0$ 人快乐
  • 每排如果坐 $1$ 人，则 $1$ 人快乐
• 为了最大化快乐，我们尽量让每排只坐 $1$ 人
• 最多可以有 $r'$ 排坐 $1$ 人，贡献 $r'$ 快乐
• 剩下的 left - r' 人必须每排坐 $2$ 人，贡献 $0$ 快乐
• 所以总快乐 = $2 \times \text{pairs} + r'$

但等等，这个公式和标程不同？检查一下：

标程中的公式是：

if(leftalone > r)
    happy += r * 2 - leftalone;
else
    happy += leftalone;

其中 r 已经是减去成对后的剩余排数。

设 rem = r - pairs（剩余排数）

• 如果 left <= rem：happy = 2*pairs + left
• 如果 left > rem：happy = 2*pairs + 2*rem - left

因为 2*rem - left = rem - (left - rem)，即单独坐的快乐减去共享造成的损失。

验证：2*pairs + 2*rem - left = (2*pairs + left) + (2*rem - 2*left) = (2*pairs + left) - 2*(left - rem) 其中 left - rem 是必须共享的人数，每共享一对损失 $2$ 快乐。

---

5. 最终算法

happy = 0
for each family a_i:
    happy += (a_i / 2) * 2
    r -= a_i / 2
    left += a_i % 2

if left <= r:
    happy += left
else:
    happy += r * 2 - left

输出 happy

---

6. 时间复杂度

• 每个测试用例 $O(n)$
• $t \le 1000$，$n \le 100$，完全可行

---

7. 示例验证

示例 1：$n=3, r=3, a=[2,3,1]$

• 家庭 1: happy += 2, r=2, left=0
• 家庭 2: happy += 2, r=1, left=1
• 家庭 3: happy += 0, r=1, left=2
• left=2 > r=1 → happy += 2*1 - 2 = 0
• 总 happy = 4 ✅

示例 2：$n=3, r=3, a=[2,2,2]$

• 每个家庭贡献 $2$，r=0, left=0
• left=0 <= r=0 → happy += 0
• 总 happy = 6 ✅

示例 3：$n=4, r=5, a=[1,1,2,2]$

• 家庭 1: happy=0, r=5, left=1
• 家庭 2: happy=0, r=5, left=2
• 家庭 3: happy=2, r=4, left=2
• 家庭 4: happy=4, r=3, left=2
• left=2 <= r=3 → happy += 2
• 总 happy = 6 ✅

---

8. 总结

核心思想：

1. 优先让同家庭的人成对坐 → 每对贡献 $2$ 快乐
2. 剩余的人尽量单独坐 → 每人贡献 $1$ 快乐
3. 如果排数不够，则每多两个人共享一排，损失 $2$ 快乐