题解

问题分析

这是一个二分答案 + 区间约束检查的复杂问题。Bessie 需要通过最少的击打次数，使得每块砖 $i$ 受到的冲击力总和 $\geq p_i$。

关键观察

1. 击打的影响：在位置 $x$ 击打一次，对位置 $i$ 的贡献是 $|i-x|$
2. 问题转化：设 $m$ 为总击打次数，我们需要判断是否存在 $m$ 次击打的方案
3. 对称性：冲击力分布具有对称性，可以利用数学性质简化问题

算法思路

二分答案 + 约束传播：

二分框架

• 二分总击打次数 $m$
• 检查是否存在 $m$ 次击打的方案满足所有 $p_i$ 要求

约束分析

对于每个位置 $i$，受到的冲击力为：

通过数学变换，可以将这个条件转化为对击打位置 $x_j$ 的约束。

核心函数说明

check(m) 函数

检查是否存在满足条件的击打方案：

• 计算每个位置 $i$ 的约束条件
• 维护可行的击打位置区间 $[l, r]$
• 返回是否所有约束相容

solve(m) 函数

更精细的检查，使用 ST 表维护区间约束：

• stl[len][i]：区间最小击打次数约束
• str[len][i]：区间最大击打次数约束
• 通过区间更新和查询验证可行性

算法步骤

1. 二分总击打次数 $m$
2. 快速检查：使用 check(m) 进行初步筛选
3. 精细验证：对候选的 $m$ 使用 solve(m) 精确验证
4. 输出最小可行的 $m$

复杂度分析

• 二分：$O(\log (2\times 10^{18}))$ 约 60 次
• 检查函数：$O(N)$ 或 $O(N \log N)$
• 总复杂度：$O(T \cdot N \log N \cdot \log MAX)$，在约束内可接受

关键技巧

1. 数学变换：将绝对值约束转化为线性不等式
2. 区间维护：使用 ST 表高效处理区间约束
3. 对称性利用：减少需要处理的情况
4. 边界处理：仔细处理除法和取整

样例验证

样例1：$[0,2,4,5,8]$

• 二分找到 $m=2$ 可行
• 击打位置 $0$ 两次，力量分布 $[0,2,4,6,8]$
• 输出正确

样例2：$[6,5,4,5,6]$

• 需要 $m=3$ 次击打
• 击打位置 $0,2,4$，力量分布 $[6,5,4,5,6]$
• 输出正确

算法标签

• 二分答案
• 约束满足
• 区间处理
• ST表
• 数学优化
• 可行性判断