数学

题目分析 本题要求的是至多选$m$次元素时能够得到的最大总价值，且对于第$i$个元素，每选择它一次，它的价值就会减少$decay[i]$，即从$value[i]$变成$value[i]-decay[i]$。 基本思路 大顶堆模拟 最直接的思路就是模拟选取元素，如果对于每一个位置都将其对应的二元组$(value[i], decay[i])$存入一个大顶堆中，那么在一次选取元素的过程中，直接取出堆顶元素即可最大化当前选取的价值。假设当前弹出的堆顶元素是$(v_i, d_i)$，那么根据题目要求，「选择元素$i$后其价值会减少$decay[i]$」，则需要将更新价值后的该元素,即二元组$(v_i-d_i, d_i)$再次压入堆中。 虽然这是一个暴力模拟方法，但依然可以加入一点优化，即在模拟$m$次选取的$while$循环中，如果某次选择元素时，整个堆中的最大值都小于0了，即可直接退出循环，因为这时再加下去也没有意义了，只会让总和变得更小。 根据上述思路，即可简单写出暴力模拟的代码如下： class Solution: def maxTotalValue(self, value: list[int], decay: list[int], m: int) -> int: n = len(value) hp = [] for i in range(n): heappush(hp, (-value[i], decay[i])) res = 0 modNum = 1_000_000_007 while m: m -= 1 cur, d = heappop(hp) cur = -cur if cur < 0: break res = (res+cur)%modNum heappush(hp, (-(cur-d), d)) return res 确实很简单，但实测只能通过221 / 561个测试用例，因此需要整个优化。 二分查找优化 如果说在整个数组中选至多$m$个元素比较困难，那么可以倒过来想，由于每一个值在选择的过程中它会变得越来越小，因此如果确定了一个最小值的界限，实际上就可以确定一个元素能够被选择的次数。具体操作是这样的： 已知要选的所有值都要大于阈值$X$，且对于元素$i$，它初始值是$v_i$，每选择它一次值就会减少$d_i$； 那么能够减少$d_i$的次数就是：$cnt=\lfloor \frac{v_i-X-1}{d_i} \rfloor$；（其中-1是为了保证减少后其值大于$X$） 因此该元素能够被选择的次数就是：$cnt+1$. 综上所述，如果$X$增大，那么总共选择的数量就一定非增(不变或减小)，否则总共选择的数量就一定非减(不变或增大)，即总共选择的数量随$X$的增大呈有序分布状态，因此可以考虑用二分查找的方式寻找一个能够满足总共选择数量小于等于$m$的最小阈值$X$。 ...

题目 在一座城市里，你需要建 n 栋新的建筑。这些新的建筑会从 1 到 n 编号排成一列。 这座城市对这些新建筑有一些规定： 每栋建筑的高度必须是一个非负整数。 第一栋建筑的高度 必须 是 0 。 任意两栋相邻建筑的高度差 不能超过 1 。 除此以外，某些建筑还有额外的最高高度限制。这些限制会以二维整数数组 restrictions 的形式给出，其中 restrictions[i] = [idi, maxHeighti] ，表示建筑 idi 的高度 不能超过 maxHeighti 。 题目保证每栋建筑在 restrictions 中 至多出现一次 ，同时建筑 1 不会 出现在 restrictions 中。 请你返回 最高 建筑能达到的 最高高度 。 思路 每一个限制都有可能影响到所有建筑物的最高高度，因此可以这样考虑： 先向右遍历一遍所有的限制，根据左侧一个限制位置的最高高度即可计算出当前限制位置的最高高度。即，如果位置i左侧最近一个限制的位置是j，且已知j的最高高度为h，那么位置i的最高高度就应该是$h+(i-j)$； 再向左遍历一遍所有的限制，按照同样的方法处理一遍所有的限制位置对应的最高高度，即可得到在所有限制下，每个位置可以达到的最高高度。 得到了每个限制位置可以达到的最高高度后，就需要计算答案了，需要注意的是，答案不仅仅是每个限制位置上的最高高度的最大值，而是每一个位置上可能的最高高度的最大值，因此需在两个已知最大高度的相邻限制位置之间求一个可能的最大高度。 如果两个相邻限制位置i和j对应的最大高度分别为$h_i$和$h_j$，那么假设在它中间的位置上有一个最大的高度best，由于题目限制了任意两栋相邻的建筑高度差最大为1，因此best必须满足以下式子： $$ (best-h_i)+(best-h_j) = j-i $$即可求出best最大为: $$ \frac{j-i+h_i+h_j}{2} $$之后，对于每两个相邻的限制位置都求一个中间的最高高度best的最大值，即可得到答案。 代码 class Solution: def maxBuilding(self, n: int, R: List[List[int]]) -> int: R.sort() R.insert(0, [1,0]) # 为了求所有的最高高度，需要在左右都加上哨兵 if R[-1][0] != n: R.append([n, n-1]) m = len(R) for i in range(1, m): R[i][1] = min(R[i][1], R[i-1][1]+(R[i][0]-R[i-1][0])) for i in range(m-2, 0, -1): R[i][1] = min(R[i][1], R[i+1][1]+(R[i+1][0]-R[i][0])) res = 0 for i in range(m-1): best = (R[i+1][0]-R[i][0]+R[i][1]+R[i+1][1])//2 res = max(res, best) return res