E. Interview - 题解

比赛与标签

比赛: Codeforces Round 859 (Div. 4) 标签: binary search, implementation, interactive, *1300 难度: *1300

喵喵，这是什么任务呀？ (题目大意)

主人，我们接到了一个有趣的任务！面前有 n 堆石子，每一堆里有 a_i 个石子。这些石子都一样重（1克），只有一个是特别的“伪装者”，它重2克，藏在某一堆里。

我们的任务就是找出这个“伪装者”在哪一堆！但是我们不能直接看，只能通过一个神奇的天平（其实是向裁判提问）来获取信息。我们可以选择任意 k 堆石子放到天平上，裁判会告诉我们这 k 堆石子的总重量。

因为裁判很忙，我们最多只能问30次问题。主人，我们能帮 Gon 在有限的次数内找到它吗？

输入输出简述:

• 输入: 首先是测试用例数 t。对于每个测试用例，第一行是石子堆数 n，第二行是 n 个数字，代表每堆石子的数量 a_i。
• 交互:
  • 提问: 输出 ? k p1 p2 ... pk，表示你想知道第 p1 到 pk 这 k 堆的总重量。然后要记得刷新缓冲区哦！
  • 回答: 读入一个整数，即你查询的那些堆的总重量。
• 最终答案: 当你确定了答案在哪一堆 m 时，输出 ! m。

用二分法锁定目标，喵！ (解题思路)

呐，主人请看，石子堆数 n 最多有 2 * 10^5，而我们只有30次提问机会。看到这个组合，是不是感觉很熟悉呀？log₂(2 * 10^5) 大约是18，这远远小于30次！这简直是在疯狂暗示我们使用 二分查找 嘛！

我们的目标是在 1 到 n 这 n 个堆中找到那个特别的堆。这不就是一个经典的查找问题嘛？我们可以对石子堆的编号进行二分查找。

假设我们当前的查找范围是 [low, high]。

1. 取中间点: 我们计算出这个范围的中间点 mid = low + (high - low) / 2。

2. 划分与提问: 我们将当前的范围 [low, high] 一分为二：左半部分 [low, mid] 和右半部分 [mid + 1, high]。然后，我们向裁判提问左半部分 [low, mid] 所有堆的总重量。

3. 分析结果: 这是最关键的一步喵！

   • 预期重量: 如果左半部分 [low, mid] 里没有那个特别的石头，那么这些堆的总重量应该等于它们石子的总数量，我们称之为“预期重量”。
   • 实际重量: 我们从裁判那里得到了这几堆的“实际重量”。
   • 比较:
     • 如果 实际重量 > 预期重量：这说明多出来的1克重量肯定来源于那个重2克的特殊石头！所以，它一定藏在我们刚刚查询的左半部分 [low, mid] 里。于是，我们就可以把查找范围缩小为 high = mid。
     • 如果 实际重量 == 预期重量：这说明我们查询的这几堆都是“乖孩子”，没有特殊石头。那么，那个“伪装者”肯定就在我们没问的右半部分 [mid + 1, high] 里啦！于是，我们把查找范围更新为 low = mid + 1。

4. 循环往复: 我们不断重复这个过程，每一次都能把查找范围缩小一半，直到 low == high。这时，我们就成功地把那个特别的石子堆给揪出来啦！

一个小优化: 为了能快速计算出任意区间 [low, mid] 的石子总数（也就是预期重量），我们可以预处理一个前缀和数组 pref。pref[i] 存的是第1堆到第 i 堆的石子总数。这样，计算 [low, mid] 区间的石子总数就只需要 pref[mid] - pref[low - 1]，时间复杂度是 O(1)，非常高效的说！

把思路变成代码吧，喵~ (代码实现)

#include <iostream>
#include <vector>
#include <numeric>

void solve() {
    int n;
    std::cin >> n;
    std::vector<long long> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }

    // 预处理前缀和数组，方便我们O(1)地查询区间石子总数，喵~
    // pref[i] 存储的是第1堆到第i堆的石子总和。
    // 输入的数组 a 是0-indexed的，所以 a[i-1] 对应第 i 堆。
    std::vector<long long> pref(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        pref[i + 1] = pref[i] + a[i];
    }

    // 开始我们的二分查找大冒险！初始搜索范围是所有堆 [1, n]。
    int low = 1, high = n;
    while (low < high) {
        // 每次都猜当前范围 [low, high] 的中间点 mid
        int mid = low + (high - low) / 2;
        
        // 构造查询：我们要问前半部分 [low, mid] 的总重量是多少
        int k = mid - low + 1;
        std::cout << "? " << k;
        for (int i = low; i <= mid; ++i) {
            std::cout << " " << i;
        }
        // 使用 endl 可以同时换行和刷新输出流，这在交互题里很重要哦！
        std::cout << std::endl;

        // 用前缀和快速算出 [low, mid] 区间里，如果没有特殊石头，应该有的石子总数（也就是预期重量）
        long long expected_sum = pref[mid] - pref[low - 1];
        
        // 读入裁判告诉我们的实际重量
        long long actual_sum;
        std::cin >> actual_sum;

        // 如果实际重量比预期的大，说明那个重1克的特殊石头就在我们问的这一半里！
        // 所以就把搜索范围缩小到 [low, mid]。
        if (actual_sum > expected_sum) {
            high = mid;
        } else {
            // 否则，说明特殊石头在另一半，也就是 [mid + 1, high]。
            low = mid + 1;
        }
    }

    // 当循环结束时，low 和 high 相遇了，这个位置就是藏着特殊石头的堆！
    // 最后，别忘了骄傲地告诉裁判我们找到的答案！
    std::cout << "! " << low << std::endl;
}

int main() {
    // 加速一下输入输出，让程序跑得更快~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

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

    return 0;
}

分析一下时间和空间吧~ (复杂度分析)

• 时间复杂度: O(N log N) 的说。 对于每个测试用例，我们首先用 O(N) 的时间预处理前缀和。之后进行二分查找，需要 log N 次查询。在每次查询中，我们需要打印出 k 个堆的编号，k 的大小与当前查询范围 (high - low) 成正比，最坏情况下是 N/2。所以总的时间复杂度是 O(N + logN * N)，也就是 O(N log N)。考虑到所有测试用例的 N 之和有上限，这个复杂度是完全可以接受的！

• 空间复杂度: O(N) 的说。 我们主要需要两个数组，一个存输入的石子数量 a，另一个存前缀和 pref，它们的大小都和 N 相关，所以空间复杂度是 O(N)。

这次探险的收获，喵~ (知识点与总结)

这次探险真是太有趣啦！我们来总结一下学到了什么吧：

1. 二分查找的应用: 二分查找不仅仅能用在排好序的数组上哦！只要一个问题满足单调性，就可以考虑二分。在这道题里，“特殊石头是否在编号小于等于 i 的堆里”这个问题的答案，随着 i 的增大，会从“否”变为“是”，这就是一种单调性！

2. 交互题的基本套路: 交互题的核心就是“提问 -> 刷新 -> 读取 -> 分析”。记住，每次向裁判提问后，一定要用 endl (C++) 或 fflush(stdout) (C) 来刷新输出缓冲区，不然裁判是收不到你的问题的，你的程序就会因为等待超时而出错哦。

3. 前缀和优化: 这是一个非常经典的小技巧！当需要频繁查询数组某个区间的和时，先花 O(N) 的时间预处理一个前缀和数组，之后每次查询都只需要 O(1) 的时间。用一点点空间换取大量的时间，超划算的！

总之，只要能从题目限制（比如查询次数）中嗅到算法的线索，再结合问题本身的性质，就能找到正确的方向啦！主人，你真棒，又解决了一道难题！喵~