CF1672E notepad.exe

「2023zimpha」二分练习题

题目传送门

交互题。

文本编辑器中有 $n$ 个单词，第 $i$ 个长度为 $l_i$。$l$ 仅对测评机可见。

文本编辑器一行一行展示文本，以空格分开相邻的两个单词，但是行末不一定有空格，即单词可以直接作为某一行的末尾。对于给定的屏幕宽度 $w$，高度 $h$ 为展示文本最少需要的行数。

如果 $w \le \max(l_i)$，那么文本编辑器将崩溃， $h = 0$ .

最多可以询问 $n + 30$ 次。每次询问宽度 $w$ 。测评机将返回 $h$。

输出最小面积，即 $min(w\times h_w)$。

$n,l_i \le 2000$

良题。

看到 $n+30$，可以猜到询问是二分+ $O(n)$ 枚举。

先二分出最小的 $w=w_1$ 满足 $h=1$，即把所有单词放在一行的长度。

此时如果有更优的 $h$，最小宽度为 $w_h$，那么一定有 $w_h \le \left\lfloor \dfrac{w_1}{h}\right \rfloor$。

对比 $h$ 行与 $1$ 行两种方案，考虑最优的情况，$h$ 行每行末尾都没有空格，那么就在 $1\sim h-1$ 行的末尾各省下了一个空格，共 $h-1$ 个，所以又有 $w_h\cdot h \ge w_1-h+1$，进一步，$w_h \ge \dfrac{w1-h+1}{h} \ge \left\lfloor \dfrac{w_1}{h}\right \rfloor$。

所以可以得到 $w_h=\left\lfloor \dfrac{w_1}{h}\right \rfloor$。

接下来，我们就可以枚举 $2 \le h \le n$，然后对 $w=\left\lfloor \dfrac{w_1}{h}\right \rfloor$ 询问，用 $w\cdot h’$ 更新答案（$h’$ 为测评机返回的数）。

Code

ll n, w, a, ans;
void solve() {
    cin >> n;
    ll l = 1, r = 2000 * 3000, mid;
    while (l <= r) {
        mid = (l + r) / 2;
        cout << "? " << mid << endl;
        cout.flush();
        cin >> a;
        if (a == 1)w = mid, r = mid - 1;
        else l = mid + 1;
    }
    ans = w;
    repp(i, n) {
        cout << "? " << w / i << endl;
        cout.flush();
        cin >> a;
        if (a)ans = min(ans, w / i * a);
    }
    cout << "! " << ans << endl;
    cout.flush();
}