题目要求在满足每个储物格至少分配 1 个单位物资、相邻储物格物资数量之差的绝对值不超过 1 的前提下,最大化编号 k 的储物格中的物资数量。由于答案具有单调性——若编号 k 的储物格能分配到 x 个物资,则也能分配到 x−1 个物资——因此可以采用二分答案的方法求解。
二分查找的思想
设定二分范围 low = 1,high = m,每次取中间值 mid,检查能否让编号 k 的储物格分配到 mid 个单位物资,并且总物资消耗不超过 m。若可行,则尝试更大的值;否则减小 mid。
检查函数 check(x)
给定一个目标值 x,我们希望验证是否有一种分配方案,使得编号 k 的储物格恰好获得 x 个物资,同时总消耗最小。为了最小化总消耗,其他储物格的物资应尽可能减少,同时满足相邻差不超过 1 的约束。
有 n 个排成一列的储物格,编号依次为 1 到 n,需要将总量为 m 个单位的物资全部放入这些储物格中。分配必须满足:每个储物格至少分到 1 个单位,且任意两个相邻储物格中的物资数量之差的绝对值不超过 1。在所有符合要求的分配方案中,我们想让编号为 k 的储物格获得尽可能多的物资。问该储物格最多可以分到多少单位物资。 约束:1≤n≤m≤109,1≤k≤n,输入均为整数。
第一行包含三个整数 n、m 和 k,分别表示储物格的数量、物资总量以及关注的储物格编号。
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册