三分法解决墙壁砌砖最小成本问题

"第三次周赛题解(1).md" 这是一道关于优化算法和成本计算的问题，题目要求在给定的墙列上通过三种操作使得所有墙的高度一致，并求出最小的代价。以下是详细的知识点解析： 1. **问题定义**： - 墙壁上有N列，每列墙的高度为h[i]。 - 操作1：添加一块砖到一列墙，花费A。 - 操作2：从一列墙移走一块砖，花费R。 - 操作3：将一列墙上的砖移到另一列墙，花费M。 - 目标：使所有墙的高度相同，求最小总成本。 2. **输入与输出**： - 输入包含四个整数N, A, R, M以及每列墙的高度数组h[i]。 - 输出是实现目标所需的最小代价。 3. **算法思想**： - 使用**三分搜索**（ ternary search）来找到最优的墙高。三分搜索是在已排序的数组中查找特定元素的搜索算法，它将搜索区间分为三部分，每次排除掉一部分不可能的区间，从而减少搜索范围。 - 定义一个函数`check(mid)`，检查给定高度`mid`时，需要多少代价来调整所有墙到`mid`高度。 4. **check()函数**： - `up`表示需要加砖的总数量，`down`表示需要减砖的总数量。 - 遍历每列墙，如果高度大于`mid`，则需要加砖，`up`增加；如果小于`mid`，则需要减砖，`down`增加。 - 当`M <= A + R`时，考虑第三个操作是否更优。如果第三个操作的代价小于第一个和第二个操作的组合，那么优先使用第三个操作。 - 计算`up`和`down`对应的操作代价，并返回总代价。 5. **代码实现**： - 使用`long long`类型存储可能的大整数。 - 定义边界`l`和`r`，并用三分搜索更新`lmid`和`rmid`，不断缩小可能的最优解区间。 - 在三分搜索过程中，比较`check(lmid)`和`check(rmid)`的结果，根据比较结果调整搜索区间。 6. **复杂度分析**： - 时间复杂度：三分搜索的时间复杂度是O(log(max_height))，其中max_height是所有墙的最大高度。 - 空间复杂度：主要消耗在输入数组和辅助变量上，是O(n)。 这个问题需要理解操作的成本模型，合理地设计搜索策略，以及有效地实现三分搜索算法。通过这个题目，我们可以学习如何在实际问题中应用搜索和优化算法，以及如何处理成本和操作效率之间的权衡。