自动搬运

查看原文

来自洛谷，原作者为

	OMG_wc 幻想家协会会长

搬运于2025-08-24 22:26:43，当前版本为作者最后更新于2020-12-02 05:08:42，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这题还是非常难想的，暴力的思路只能解决 Subtask 1和4。

总觉得情况很多复杂无比，对于多余的水一直很纠结该怎么放，有一个无穷大的容器可以接就好了。

但是想不出来并不影响我写题解

为了简化问题，先假设有一个无穷大的桶可以接水，也就是允许清空任意桶。为什么会想到清空呢？因为清空后的桶就沦落为工具人（桶）了。

首先 $a_1$ 是直接能测出来的~~（地球人都知道吧）~~，测完后把 $a_1$ 清空，这样 $a_2$ 也能测出来了：

执行？ 2 1 ，如果第一个桶没满，说明 $a_2=0$，测完了；如果第一个桶满了，说明 $a_2\ge 1$，这时候你需要把水倒回去，所以再执行? 1 2，这个返回值可以忽略，最后执行? 2 2 就能知道 $a_2$ 是 $1$ 还是 $2$ 了。

这样测出 $a_2$ 后，也把 $a_2$ 清空，用上面方法能测出 $a_3$：分别执行? 3 1、? 3 2、? 3 3（除了最后一次，每次测完还需倒回去）。

这样一算的话，测到 $a_n$，不算清空操作，需要 $1+3+5+...+ 2n-1$次，显然超过限制了。

其实没必要从小到大一个个枚举，换成二分就行了，这样算起来是不超过 $\sum\limits_{i=1}^n2 \lceil\log_2 (i+1)\rceil$ 次。

现在的问题是，不存在一个无穷大的容器可以清空，这样只能把水往后倒了。

还是先从最最最简化的问题开始考虑：

假设每次清空都倒到第 $n$ 个桶，并且前 $n-1$ 个桶清空完毕后，第 $n$ 个桶还是不满的。

这样，我们最后用二分测出最后一个桶的水量 ，其实是多了 $\sum\limits_{i=1}^{n-1} a_i$ 这么多的，把这部分减掉就是真实的 $a_n$。

如果情况稍稍复杂一点：

清空第 $k$ 个桶的时候，第 $n$ 个桶突然满了

这时候，第 $k$ 个桶可能没倒完，可以用二分测出还剩下 $t$ 个水没清空，这样实际倒进去的是 $a_k-t$ 这么多水，所以可以得到 $a_n=n+t-\sum\limits_{i=1}^{k} a_i$。

然后剩余的 $t$ 个水再倒进 $n-1$ 这个桶里（若 $k=n-1$ 就不用清空了），如果满了可以同样处理：

设一个变量 $pos$ 表示当前清空是往这个桶倒，若 $k=pos$ 就不用清空了。

现在思路就清晰了，在循环计算第 $k$ 个桶的过程中，不仅把 $[1,k]$ 的水量算出来了，还算了一个后缀 $[pos+1,n]$的水量，当两者相遇时就结束循环。而每一次二分，就能得到一个桶的结果（前面的或者后面的），二分总的询问次数可以算出来最多有 $17974$ 次，加上 $999$ 次清空，总和在 $20000$ 次限制范围内。

参考代码如下：

int ans[N];
int pour(int x, int y) {
    int w;
    printf("? %d %d\n", x, y);
    fflush(stdout);
    scanf("%d", &w);
    return w;
}
int cal(int i) {
    int l = 1, r = i + 1;
    while (l < r) {
        int mid = l + r >> 1;
        if (pour(i, mid) == 0)
            r = mid;
        else
            l = mid + 1;
        pour(mid, i);
    }
    return l - 1;
}
int main() {
    int n;
    scanf("%d", &n);
    int pos = n;
    for (int i = 1; i <= pos; i++) {
        int now = cal(i);
        ans[i] += now;
        while (i != pos) {
            if (pour(i, pos) == 0) {
                ans[pos] -= now;
                break;
            }
            int tmp = now;
            now = cal(i);
            ans[pos] += pos - (tmp - now);
            pos--;
        }
    }
    printf("!");
    for (int i = 1; i <= n; i++) printf(" %d", ans[i]);
    puts("");
    return 0;
}