题目分析

本题要求从一个未知的单调递增序列中，选择 $K$ 个数，使得它们的和在 $[A, 2A]$ 范围内。我们最多只能查询 $S$ 个元素的值。这是一个典型的交互式选择问题，需要在有限的查询次数内找到满足条件的解。

关键观察

1. 序列的单调性： 序列 $x$ 是单调递增的，即 $x_1 < x_2 < \dots < x_N$。这一性质是关键，允许我们进行二分搜索和范围推断。

2. 条件限制：

需要选择恰好 $K$ 个数

和必须在 $[A, 2A]$ 范围内

最多查询 $S$ 个元素的值

3. 贪心策略：

最小的可能和：选择前 $K$ 个数 $x_1, x_2, \dots, x_K$

最大的可能和：选择后 $K$ 个数 $x_{N-K+1}, \dots, x_N$

如果最小和已经大于 $2A$ 或最大和小于 $A$，则无解

算法思路

1. 初步检查与处理

算法首先查询前 $K$ 个元素：

如果这 $K$ 个数的和已经在 $[A, 2A]$ 范围内，直接返回答案

如果第 $K$ 个元素 $x_K \ge A$，那么最小的 $K$ 个元素之和至少为 $K \cdot x_K \ge K \cdot A$，当 $K \ge 2$ 时可能超过 $2A$，需要进一步检查

2. 二分搜索关键位置

通过二分搜索找到第一个大于 $A$ 的元素位置：

int l = K + 1, r = N + 1;
while (l < r) {
    int mid = l + r >> 1;
    if (skim(mid) > A) r = mid;
    else l = mid + 1;
}

这个位置记为 $r$，满足 $x_r > A$ 且 $x_{r-1} \le A$（如果存在）。

3. 替换策略

情况 1： 用第 $r$ 个元素替换第 $K$ 个元素

新的和为：$(x_1 + \dots + x_{K-1}) + x_r$

由于 $x_r > A$，而前 $K-1$ 个元素的和较小，总和可能在 $[A, 2A]$ 内

检查条件：如果 $\text{sum} - x_K + x_r \le 2A$，则成功

情况 2： 滑动窗口替换

如果情况 1 不满足，尝试用后面的元素替换前面的多个元素：

从位置 $i = r-1$ 开始，向前尝试最多 $K$ 个位置

每次用 $x_i$ 替换掉当前集合中最小的元素

随着替换的进行，总和逐渐增大

当总和首次达到 $\ge A$ 时，检查是否 $\le 2A$

正确性证明

1. 单调性的利用：

序列单调递增，因此替换较大元素会增大总和

二分搜索正确找到第一个大于 $A$ 的元素

2. 替换策略的正确性：

情况 1：用一个大元素 $x_r (>A)$ 替换 $x_K$，可能使总和进入目标区间

情况 2：逐步替换，总和单调递增。由于序列递增，每次替换都会增加总和

3. 边界情况处理：

如果 $x_K \ge A$ 且前 $K$ 个元素和超过 $2A$，则可能无解

如果所有元素都太小，无法达到 $A$，则无解

4. 查询次数控制：

最多查询 $K$（前 $K$ 个）+ 1（二分搜索）+ $K$（滑动窗口）= $2K+1$ 次

由于 $K \le 10$，最多 21 次查询，远小于 $S$（$S \le 10^5$）

时间复杂度

• 查询次数：$O(K)$，最多约 $2K+1$ 次

• 计算复杂度：$O(K)$

• 总复杂度：$O(K)$，非常高效

AC代码

#include <bits/stdc++.h>
#include "books.h"
#define pb push_back
using namespace std;
typedef long long ll;
typedef vector<int> vec;
const int N = 1e5 + 10;
ll x[N], sum;
void solve(int N, int K, ll A, int S) {
    vec ans;

    for (int i = 1; i <= K; i ++) {
        sum += (x[i] = skim(i));
        ans.pb(i);
    }

    if (sum >= A && sum <= A * 2)
        answer(ans);

    if (x[K] >= A)
        impossible();

    int l = K + 1, r = N + 1;

    while (l < r) {
        int mid = l + r >> 1;

        if (skim(mid) > A)
            r = mid;
        else
            l = mid + 1;
    }

    if (r <= N && sum - x[K] + skim(r) <= 2 * A) {
        ans.pop_back();
        ans.pb(r);
        answer(ans);
    }

    for (int i = l - 1; i >= max(l - K, K + 1); i --) {
        sum += skim(i) - x[l - i];
        ans.erase(ans.begin()), ans.pb(i);

        if (sum >= A)
            answer(ans);
    }

    impossible();
}