问题分析

我们需要将 $s$ 名防御者分配到 $n$ 段墙上，每段墙有 $a_i$ 名攻击者，每名防御者能击退 $k_i$ 名攻击者。目标是最小化攻破防守的攻击者总数。

核心思路

关键观察

对于任意一段墙 $i$：

• 如果我们分配 $x_i$ 名防御者，那么：
  • 如果 $a_i \leq x_i \times k_i$，该段不会被攻破
  • 如果 $a_i > x_i \times k_i$，有 $a_i - x_i \times k_i$ 名攻击者攻破

贪心策略

这是一个典型的贪心分配问题。我们可以将问题转化为：如何用有限的防御者资源来"抵消"最多的攻击者。

核心思想：优先使用防御者去抵消那些"性价比最高"的攻击者。

算法实现

1. 问题转化

将每段墙的防御分解为多个"防御单元"：

• 每个完整的防御单元：需要 1 名防御者，能抵消 $k_i$ 名攻击者
• 最后一个不完整的防御单元：需要 1 名防御者，能抵消 $(a_i \bmod k_i)$ 名攻击者

2. 贪心排序

将所有防御单元按照其"防御效率"（即能抵消的攻击者数量）从大到小排序：

• 完整的防御单元：效率为 $k_i$
• 不完整的防御单元：效率为 $a_i \bmod k_i$

3. 最优分配

按效率从高到低依次分配防御者：

• 如果防御者充足，分配整个防御单元
• 如果防御者不足，分配部分防御单元

复杂度分析

• 预处理：$O(n)$ 生成防御单元
• 排序：$O(n \log n)$ 对 $2n$ 个防御单元排序
• 分配：$O(n)$ 贪心分配
• 总复杂度：$O(n \log n)$，适用于 $n \leq 10^5$ 的数据范围

算法总结

本题的解法基于以下几个关键点：

1. 问题转化：将复杂的分配问题转化为标准的贪心选择问题
2. 防御单元分解：将每段墙的防御需求分解为多个独立的防御决策
3. 效率优先：按照防御效率从高到低分配有限的防御资源
4. 完整性处理：分别考虑完整防御单元和不完整防御单元的不同特性