猜数（IO交互版）的题解

记住只在没有思路时使用题解，不要从它复制粘贴代码。请尊重题目和题解的作者。
在解题之前提交题解的代码会导致封禁。

作者： admin

概述

本题要求在未知整数 $n \in [1, 10^9]$ ~n \in [1, 10^9]~ 上，用不超过 $50$ ~50~ 次「猜一个数、得到它与答案大小关系」的询问确定 $n$ ~n~。核心解法是二分查找：每次询问当前候选区间的中点，按反馈把区间折半， $30$ ~30~ 次以内必然命中。

分析

核心观察

反馈与猜测值相对答案的大小是一一对应的：返回 $-1$ ~-1~ 说明猜的数小于答案，返回 $1$ ~1~ 说明猜的数大于答案，返回 $0$ ~0~ 说明命中。因此每次询问都能排除掉「不可能包含答案」的那一半区间——这正是二分查找所需的全部信息。

思路

设当前候选区间为 $[lo, hi]$ ~[lo, hi]~，取中点 $mid = \lfloor (lo + hi) / 2 \rfloor$ ~mid = \lfloor (lo + hi) / 2 \rfloor~ 并询问 $mid$ ~mid~：

返回 $0$ ~0~：命中，答案就是 $mid$ ~mid~，立刻结束程序；
返回 $-1$ ~-1~： $mid$ ~mid~ 小于答案，答案落在 $(mid, hi]$ ~(mid, hi]~，令 $lo = mid + 1$ ~lo = mid + 1~；
返回 $1$ ~1~： $mid$ ~mid~ 大于答案，答案落在 $[lo, mid)$ ~[lo, mid)~，令 $hi = mid - 1$ ~hi = mid - 1~。

每次询问后区间长度至少减半（ $hi - lo + 1$ ~hi - lo + 1~ 从 $m$ ~m~ 变为至多 $\lceil m/2 \rceil$ ~\lceil m/2 \rceil~）。初始区间长度为 $10^9$ ~10^9~，而

$\displaystyle 2^{30} = 1073741824 > 10^9$

所以最多 $\lceil \log_2 10^9 \rceil = 30$ ~\lceil \log_2 10^9 \rceil = 30~ 次询问就能把区间缩到单个整数，远小于题面允许的 $50$ ~50~ 次。当 $lo > hi$ ~lo > hi~ 时区间为空，说明之前的判断出现了矛盾，正常情况下不会发生。

具体示例

以 $n = 2333$ ~n = 2333~ 为例，二分过程的前几步：

区间 $[lo, hi]$ ~[lo, hi]~	$mid$ ~mid~	反馈	区间变化
$[1, 10^9]$ ~[1, 10^9]~	$500000000$ ~500000000~	$-1$ ~-1~	$lo = 500000001$ ~lo = 500000001~
$[500000001, 10^9]$ ~[500000001, 10^9]~	$750000000$ ~750000000~	$-1$ ~-1~	$lo = 750000001$ ~lo = 750000001~
$[750000001, 10^9]$ ~[750000001, 10^9]~	$875000000$ ~875000000~	$1$ ~1~	$hi = 874999999$ ~hi = 874999999~
$[750000001, 874999999]$ ~[750000001, 874999999]~	$812500000$ ~812500000~	$1$ ~1~	$hi = 812499999$ ~hi = 812499999~

每次区间长度减半，约 $30$ ~30~ 次后区间收缩到 $2333$ ~2333~，此时询问返回 $0$ ~0~，程序结束。

算法步骤

令 lo 为 $1$ ~1~，hi 为 $10^9$ ~10^9~。
当 lo <= hi 时重复：计算 mid = lo + (hi - lo) / 2，输出 mid 并换行，随后刷新缓冲区。
从标准输入读入反馈 res。
若 res 为 $0$ ~0~，直接结束程序。
若 res 为 $-1$ ~-1~，令 lo = mid + 1；否则（res 为 $1$ ~1~）令 hi = mid - 1，回到第 2 步。

复杂度分析

时间：询问次数为 $O(\log V)$ ~O(\log V)~，其中 $V = 10^9$ ~V = 10^9~，即最多约 $30$ ~30~ 次；每次询问只做常数次算术与输入输出。
空间： $O(1)$ ~O(1)~。只需要 lo、hi、mid、res 四个变量。

实现注意事项

每次输出后必须刷新缓冲区。C++ 用 std::endl（换行并刷新）或 std::cout << std::flush，Python 用 print(mid, flush=True)。少写刷新会让评测程序收不到询问，双方互相等待，最终表现为超时。
返回 $0$ ~0~ 表示猜中，此时应立即结束程序，不要再输出任何内容；继续询问会因为评测程序已经退出而读到文件结束符。
$-1$ ~-1~ 的含义是「猜的数小于答案」，也就是答案在右半边，更新的是 lo；把方向写反会让区间朝错误方向收缩。
询问的整数必须落在 $[1, 10^9]$ ~[1, 10^9]~ 内，越界询问会被判定为答案错误。
二分结束时 lo > hi，说明程序逻辑有误；正常情况下一定会在某次询问返回 $0$ ~0~ 时提前结束。

源代码

#include <iostream>

int main() {
    long long lo = 1, hi = 1000000000LL;
    while (lo <= hi) {
        long long mid = lo + (hi - lo) / 2;
        // std::endl 输出换行并刷新缓冲区，缺少刷新会导致交互死锁
        std::cout << mid << std::endl;

        int res;
        if (!(std::cin >> res)) {
            break;
        }
        if (res == 0) {
            return 0;
        }
        if (res == -1) {
            lo = mid + 1;  // mid 小于答案，答案在右半区间
        } else {
            hi = mid - 1;  // mid 大于答案，答案在左半区间
        }
    }
    return 0;
}

import sys


def main():
    lo, hi = 1, 10 ** 9
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        # flush=True 输出换行并刷新缓冲区，缺少刷新会导致交互死锁
        print(mid, flush=True)

        res = int(sys.stdin.readline())
        if res == 0:
            return
        if res == -1:
            lo = mid + 1  # mid 小于答案，答案在右半区间
        else:
            hi = mid - 1  # mid 大于答案，答案在左半区间


main()

目前没有评论。