解题思路
题目要求在满足每个储物格至少分配 1 个单位物资、相邻储物格物资数量之差的绝对值不超过 1 的前提下,最大化编号 k 的储物格中的物资数量。由于答案具有单调性——若编号 k 的储物格能分配到 x 个物资,则也能分配到 x−1 个物资——因此可以采用二分答案的方法求解。
-
二分查找的思想
设定二分范围 low = 1,high = m,每次取中间值 mid,检查能否让编号 k 的储物格分配到 mid 个单位物资,并且总物资消耗不超过 m。若可行,则尝试更大的值;否则减小 mid。
-
检查函数 check(x)
给定一个目标值 x,我们希望验证是否有一种分配方案,使得编号 k 的储物格恰好获得 x 个物资,同时总消耗最小。为了最小化总消耗,其他储物格的物资应尽可能减少,同时满足相邻差不超过 1 的约束。