G1. Ruler (easy version) - 题解

比赛与标签

比赛: Codeforces Round 964 (Div. 4) 标签: binary search, interactive, *1500 难度: *1500

题目大意喵~

主人你好呀~ 这是一道有趣的交互题哦！

我们有一个神秘的数字 x（它的范围是 2 到 999），它藏在一把有点奇怪的尺子里。这把尺子是这样工作的喵：

如果你要测量的长度 y 小于 x，尺子会正确地显示长度 y。
如果你要测量的长度 y 大于或等于 x，尺子就会“犯迷糊”，显示一个错误的长度 y + 1。

我们的任务就是找出这个神秘的 x！为了做到这一点，我们可以向系统进行查询。每次查询，我们可以提供一个矩形的长 a 和宽 b（格式是 ? a b）。系统会用这把奇怪的尺子分别测量 a 和 b，得到测量值 m(a) 和 m(b)，然后返回它们的乘积 m(a) * m(b) 给我们。

我们需要在最多 10 次查询内，准确地找到 x 的值，然后用 ! x 的格式告诉系统，的说！

思路分析喵~

这道题的查询次数限制是 10 次，而 x 的范围是 [2, 999]，差不多是 1000。看到这个组合，聪明的猫娘我呀，第一反应就是——二分查找！因为 log₂(1000) 大约就是 10，正好能对上，喵~

但是，怎么用 ? a b 这种返回乘积的查询来进行二分呢？这就要动动小脑筋啦！

核心思想: 我们的目标是利用查询来判断一个我们猜测的数 k 是大于、小于还是等于真正的 x。如果能做到这一点，二分查找就可行了。问题的关键在于，查询 ? a b 返回的是 m(a) * m(b)，是一个乘积，我们很难直接从中分离出关于 x 的信息。
关键观察: 我们来想一想，有没有什么办法能让这个乘法变得简单呢？比如说，让其中一个乘数变成 1？让我们试试查询 ? 1 k 会发生什么，呐。
- 题目告诉我们，秘密数字 x 的范围是 2 ≤ x ≤ 999。
- 这意味着，我们查询的边长 1 永远都小于 x (1 < x)！
- 根据尺子的规则，当测量长度小于 x 时，结果是准确的。所以，m(1) 的值永远都是 1。
- 那么，查询 ? 1 k 返回的结果就是 m(1) * m(k) = 1 * m(k) = m(k)。喵呀！这太棒了！通过查询 ? 1 k，我们就能直接得到长度 k 的测量值 m(k)！这个发现是解决问题的突破口的说！
算法流程: 现在我们有了一个强大的工具，可以检查任意 k 的测量值，二分查找的流程就非常清晰了：
- 我们要在 [2, 999] 的范围里寻找 x。设我们的搜索区间为 [l, r]，初始时 l = 2, r = 999。
- 在循环中，我们取中间值 mid = l + (r - l) / 2。
- 我们向系统发起查询 ? 1 mid，然后读取返回的结果 response。
- 现在分析 response：
  - 如果 response == mid：这说明 m(mid) 等于 mid。根据规则，这只有在 mid < x 的时候才会发生。既然 mid 都比 x 小，那 x 肯定在 mid 的右边。所以，我们就可以放心地把搜索区间的左边界更新为 l = mid + 1。
  - 如果 response == mid + 1：这说明 m(mid) 等于 mid + 1。根据规则，这发生在 mid ≥ x 的时候。这说明 x 可能就是 mid，或者比 mid 还要小。所以，我们要把搜索区间的右边界更新为 r = mid，来继续在左半边寻找。
- 我们不断重复这个过程，l 和 r 会不断靠近，直到 l == r。此时，它们共同指向的值，就是我们苦苦寻找的那个最小的、使得 m(k) = k + 1 的 k，也就是我们的答案 x 啦！
- 最后，我们愉快地输出 ! l 就大功告成啦，喵~

代码实现

cpp

#include <iostream>
#include <cstdlib>

// 这个函数处理单个测试用例喵~
void solve() {
    // 我们要找的秘密数字 x 在 [2, 999] 这个范围里。
    // 用二分查找来找到 x 是再好不过的选择了！
    int l = 2, r = 999;

    // 我们二分的依据是查询 "? 1 k"。
    // 因为 x >= 2，所以长度 1 永远小于 x，它的测量值 m(1) 总是 1。
    // 那么查询 "? 1 k" 就会返回 m(1) * m(k) = 1 * m(k) = m(k)。
    // - 如果 m(k) = k，说明 k < x。
    // - 如果 m(k) = k + 1，说明 k >= x。
    // "k >= x" 这个条件是单调的：对于 k < x 的值是 false，对于 k >= x 的值是 true。
    // 我们要找的就是第一个让这个条件为 true 的 k，也就是 x 本身。
    // 这是典型的二分查找问题，寻找 F...FT...T 序列中第一个 T 的位置，的说。
    while (l < r) {
        int mid = l + (r - l) / 2;

        // 发起查询，记得要刷新缓冲区哦！
        std::cout << "? 1 " << mid << std::endl;
        
        int response;
        std::cin >> response;

        if (response == -1) {
            // 如果返回 -1，说明查询出错了（比如查询次数超了）。
            // 按照题目要求，要立刻退出程序。
            exit(0);
        }

        if (response == mid + 1) {
            // 这意味着 m(mid) = mid + 1，所以 mid >= x。
            // 答案可能是 mid，也可能在 mid 的左边。
            // 所以我们把搜索范围缩小到左半部分 [l, mid]。
            r = mid;
        } else { // response == mid
            // 这意味着 m(mid) = mid，所以 mid < x。
            // 答案肯定在 mid 的右边。
            // 所以我们把搜索范围缩小到右半部分 [mid + 1, r]。
            l = mid + 1;
        }
    }

    // 当循环结束时，l 和 r 相遇了，它们指向的就是最终的答案 x！
    std::cout << "! " << l << std::endl;
}

int main() {
    // 用这两行代码可以让 C++ 的输入输出快一点，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

复杂度分析

时间复杂度: O(log R) 的说。这里的 R 是 x 的可能取值范围大小，大约是 1000。每次二分查询都会将搜索范围减半，所以总的查询次数是对数级别的。对于 R=999，log₂(999) 约等于 9.96，所以最多 10 次查询就足够了，完全符合题目要求。
空间复杂度: O(1) 的说。我们在解决问题时只用了 l, r, mid 等几个变量，占用的空间是固定的，不会随着问题规模的增大而增大，所以是常数空间复杂度。

知识点总结

解决这个问题，我们主要用到了这些可爱的知识点，方便主人复习，的说喵~

交互式问题 (Interactive Problem): 学会了如何通过标准输入输出与判题系统进行一问一答的交流，并且记得每次输出后都要 flush 缓冲区！
二分查找 (Binary Search): 这是解题的核心算法。特别是这种在单调序列中寻找“分界点”的二分模型，非常经典和常用。
问题转化 (Problem Reduction): 将一个看起来复杂的查询（返回乘积），通过巧妙地固定一个参数（a=1），转化成一个简单的查询（直接返回测量值），这是解题的智慧所在，呐！

G1. Ruler (easy version) - 题解 ​

比赛与标签 ​

题目大意喵~ ​

思路分析喵~ ​

代码实现 ​

复杂度分析 ​

知识点总结 ​