【语法】
一、隐蔽陷阱
把 1000 个金币打包成不超过 25 个包裹,单包容量多大才够?从 1 开始逐个容量去试要跑上千次;改成对半猜,却总在边界上停不下来——hi 来回横跳,mid 值反复出现,典型的区间不收缩。
二、底层原理
提问换一种问法:容量定为 cap 时,包裹数 math.ceil(1000/cap) 是否不超过 25?cap 越大包越少,判定结果单调,这正是二分的前提。区间 [lo, hi] 每次取 mid 检验:满足则答案可能是 mid,hi 收到 mid;不满足则 lo 跳到 mid+1。循环条件 lo < hi,收敛后 lo 即最小容量。
三、正确代码
错误写法:
while lo <= hi do
if ok(mid) then lo = mid + 1 end
-- 满足时也把 lo 推过去,正确解被跳过
end
正确写法:
local lo, hi = 1, 1000
while lo < hi do
local mid = math.floor((lo + hi) / 2)
if math.ceil(1000 / mid) <= 25 then
hi = mid
else
lo = mid + 1
end
end
print(lo) -- 40:每包 40 个,恰好 25 包
四、引擎验证
答案是 40:40 一包正好 25 包;39 一包要 26 包超限。区间从 1000 宽度收缩到 1 只用了 9 轮判定。
五、FAQ
问:判定不单调能用吗?
答:不能,先确认"越大越容易满足"或反过来,否则二分收敛到错误点。
问:mid 要不要加一?
答:lo+hi 除 2 向下取整,配合 hi=mid、lo=mid+1 的配对,区间必然缩小,不会打转。
全站技术干货持续更新:996 引擎 / Lua 实战帖,语法、参数与示例一篇讲透。进入文章地图 · 查看全部 →
【游戏】 一、规则机制 隐蔽的坑:折叠列表收起分组时只把子项 setVisible(false),占位还留在原地,列表下半截…
【语法】 一、机制原理 一行代码拆解:a, b = b, a % b。最大公约数的辗转相除法:两数相除取余数,余数再与除数继…
【游戏】 一、规则机制 线上事故:聊天里 @ 了某人,消息混在普通流水里,对方根本没注意,集合迟到的锅全甩给没提醒。点名提醒…
【游戏】 一、规则机制 一行定骨架:text = LANG[cur][key] or LANG.zh[key]。多语言文案的…
【语法】 一、机制原理 抛个坑:模板"$(name),您的$(item)已到账"这种带命名槽位的文案怎么填值?string.…
【游戏】 一、规则机制 抛个坑:横屏竖屏一切界面,控件坐标全按竖屏摆,一旋转错位满屏——适配该怎么做?两条策略配合:界面元素…