题解 P7109 【滴水不漏】

· · 题解

这题还是非常难想的，暴力的思路只能解决 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;
}