F1. Guess the K-th Zero (Easy version) - 题解

比赛与标签

比赛: Codeforces Round 719 (Div. 3) 标签: binary search, interactive 难度: *1600

喵喵，这是什么题目呀？

主人你好呀~ 这是一道非常有趣的交互题哦！(ฅ'ω'ฅ)

想象一下，有一个长度为 n 的神秘数组，里面只藏着 0 和 1。我们的任务是，在最多 20 次询问内，找到从左边数第 k 个 0 的位置在哪里，喵~

我们可以向系统发起一种询问：? l r，系统会告诉我们数组里从第 l 个位置到第 r 个位置所有数字的和。

因为数组里只有 0 和 1，所以这个和其实就是区间 [l, r] 中 1 的个数啦！那么，这个区间里 0 的个数就是 (r - l + 1) - (1的个数)，是不是很简单呐？

在这道简单版本的题目里，我们只需要找到一次第 k 个 0 的位置，然后用 ! x 的格式告诉系统答案 x 就好啦！

解题思路喵~

一看到查询次数限制得这么紧（20次），而 n 又可以很大（最大 20 万），我们的猫猫直觉就告诉我们，这一定是二分查找的舞台，喵！( •̀ ω •́ )✧

我们要找的是一个位置，所以我们可以对答案的可能范围 [1, n] 进行二分查找。

让我们的二分区间是 [low, high] 吧，初始时 low = 1, high = n。

每次我们取一个中间位置 mid = (low + high) / 2。现在的问题是，怎么判断真正的答案是在 mid 的左边还是右边呢？

我们可以利用一个单调的性质：数组前缀中 0 的数量是随着前缀长度增加而单调不减的。也就是说，[1, p] 区间里 0 的数量，肯定不会比 [1, p-1] 区间里 0 的数量少，对吧？

所以，我们可以向系统询问 ? 1 mid，得到区间 [1, mid] 里 1 的数量，记为 sum。那么，这个区间里 0 的数量就是 zeros = mid - sum。

接下来就是二分的核心判断啦：

如果 zeros >= k：这说明从 1 到 mid 的这部分已经包含了至少 k 个 0。那么，我们要找的第 k 个 0 肯定就在这个区间 [1, mid] 里！它可能是 mid，也可能在 mid 的左边。所以，我们可以大胆地把搜索范围缩小到 [low, mid]，也就是 high = mid。
如果 zeros < k：这说明从 1 到 mid 的所有 0 加起来都还不够 k 个。那第 k 个 0 肯定在 mid 的右边啦！所以，我们的搜索范围就可以更新为 [mid + 1, high]，也就是 low = mid + 1。

我们就这样不断地把搜索区间减半，直到 low 和 high 相遇。当 low == high 时，这个位置就是我们千辛万苦寻找的最小的 p，满足 [1, p] 区间内至少有 k 个 0。这不就是第 k 个 0 的准确位置嘛！

最后，只要开心地输出 ! low 就大功告成啦，喵~

代码实现喵！

cpp

#include <iostream>
#include <cstdlib> // 为了 exit(0)

using namespace std;

int main() {
    // 读入数组长度 n 和 查询次数 t (虽然 t 在这题里总是 1)
    int n, t;
    cin >> n >> t;
    
    // 读入我们要找的是第 k 个 0
    int k;
    cin >> k;

    // 初始化二分查找的左右边界
    int low = 1, high = n;
    
    // 当 low 和 high 没有相遇时，继续二分
    while (low < high) {
        // 计算中间位置
        int mid = low + (high - low) / 2; // 用这种写法防止整数溢出，是好习惯喵~
        
        // 发起询问：查询区间 [1, mid] 的和
        cout << "? 1 " << mid << endl;
        // 交互题一定要记得刷新缓冲区！不然系统收不到你的消息哦！
        cout.flush();

        // 读取系统返回的和 (也就是 1 的数量)
        int sum;
        cin >> sum;

        // 如果返回 -1，说明查询格式错误，立刻退出
        if (sum == -1) {
            exit(0);
        }

        // 计算区间 [1, mid] 中 0 的数量
        // 区间长度是 mid，1 的数量是 sum，所以 0 的数量就是 mid - sum
        int zeros = mid - sum;

        if (zeros >= k) {
            // 如果 [1, mid] 中的 0 已经足够 k 个，
            // 说明第 k 个 0 在 mid 或者 mid 的左边。
            // 所以我们将搜索上界 high 缩小到 mid
            high = mid;
        } else {
            // 如果 [1, mid] 中的 0 不足 k 个，
            // 说明第 k 个 0 一定在 mid 的右边。
            // 所以我们将搜索下界 low 提高到 mid + 1
            low = mid + 1;
        }
    }

    // 循环结束时, low == high, 这就是最终答案的位置
    cout << "! " << low << endl;
    // 别忘了最后也要刷新缓冲区！
    cout.flush();

    return 0;
}

复杂度分析的说

时间复杂度: O(log n) 的说。我们的二分查找每次都将搜索范围 [1, n] 减半，总共需要进行 log₂(n) 次查询。对于 n <= 2 * 10^5，log₂(n) 大约是 18，远小于 20 次的限制，非常安全！
空间复杂度: O(1) 的说。我们只用了几个变量来存储边界和中间值，没有使用额外的数组或者数据结构，所以是常数空间复杂度，非常节省内存呐！

知识点与总结

这道题真是太棒了，可以让我们学到好多东西呢！

交互式问题: 第一次接触的主人要记住，和系统一问一答时，每次输出后都要用 cout.flush() 或 fflush(stdout) 来刷新缓冲区，不然你的程序会因为等待对方而超时（Idleness limit exceeded）哦！
二分查找答案: 这是一个超级有用的思想！当你发现答案具有单调性时（比如本题中，“位置 p 是否包含第 k 个 0” 这个问题的答案，从 "否" 变为 "是" 之后就不会再变回 "否"），就可以用二分来快速定位这个“临界点”。
转换问题: 把“查询区间和”巧妙地转换为“计算区间内 0 的数量”，是解题的关键一步。有时候换个角度看问题，就会豁然开朗的说！

希望这篇题解能帮到你，祝主人刷题愉快，天天AC！喵~ (´,,•ω•,,)♡

F1. Guess the K-th Zero (Easy version) - 题解 ​

比赛与标签 ​

喵喵，这是什么题目呀？ ​

解题思路喵~ ​

代码实现喵！ ​

复杂度分析的说 ​

知识点与总结 ​