1000ms

Difficulty: 5

所属公司 : 饿了么

时间 :2025年9月19日(算法方向)

算法与标签>模拟

会员或题库专享

请先，开通会员或购买题库饿了么机考编程题库，可解锁完整内容。

购买饿了么机考编程题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（饿了么机考编程题库），可解锁完整内容。

购买题库开通会员

思路

这个问题本质上是要求我们模拟题目中描述的二分搜索过程。我们并不知道秘密数字 $x$ 是什么，但我们知道每一次比较的结果。我们可以利用这些结果来逐步缩小搜索范围，就像“天才”那一方所做的一样。

初始化范围：我们和“笨蛋”一样，从相同的初始范围开始。设置下界 $l=1$ 和上界 $r=2^{20}$ 。 $2^{20}$ 的具体数值是 $1048576$ 。
模拟猜测过程：我们得到了一个包含 $20$ 个字符的结果字符串。我们需要从第一个字符开始，遍历这个字符串，模拟每一轮的决策。
更新边界：对于字符串中的每一个字符（假设是第 $i$ 次猜测的结果），我们执行以下操作：

题目内容

天才选择了一个秘密整数 $x$ ，其范围为 $[1,2^{20}]$ 。笨蛋按固定的二分策略进行 $20$ 次猜测。每次猜测流程如下：

维护当前可能范围 $[l,r]$ (初始 $l=1,r=2^{20}$ ，均为闭区间)；
取中位数 $g=[\frac{l+r+1}{2}]$ 作为本轮猜测；