CF1672E notepad.exe 做题记录

这是一道交互题。

在文本编辑器里有 $n$ 个单词，其中第 $i$ 个单词的长度为 $l_i$ ($1 \le l_i \le 2000$)。$l$ 仅对测评机可见。

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

更正式地，设文本编辑器的宽度为 $w$ 。设 $a$ 是一个长度为 $k + 1$ 的序列，其中 $1 = a_1 < a_2 < ... < a_{k+1} = n + 1$. $\{a_n\}$ 是一个合法的序列当且仅当，$\forall 1 \le i \le k, l_{a_i} + 1 + l_{a_{i + 1}} + 1 + \dots + 1 + l_{a_{i+1} - 1} \le w$。 那么，$h$ 就是所有合法的 $\{a_n\}$ 中最小的 $k$.。

注意，如果 $w \le \max(l_i)$，那么文本编辑器将不能显示所有的文字并且崩溃，此时 $h = 0$。

你可以做 $n + 30$ 次询问。每次询问中，输出宽度 $w$ . 测评机将返回 $h_w$ ，即当宽度为 $w$ 的最小高度。

请找到文本编辑器的最小面积，即求 $min(w\times h_w | 1 \le w \le n)$。

看到 $n+30$ 次询问，容易猜到应该是用 $30$ 次操作求一个关于值域的东西，剩下 $n$ 次操作求出答案。

考虑 $30$ 次操作能求出什么，显然可以二分求出：

1. 最长的单词长度 $mxlen$；
2. $h=1$ 时最小的 $w$，即所有单词的长度和加上 $n-1$，设它为 $L$。

$mxlen$ 好像没什么用，那么考虑 $L$ 的用途。

若 $h=i$ 且此时更优秀，那么 $w$ 的最大的情况只能是 $\lfloor\frac{L}{i}\rfloor$，并且由于 $h=i$ 时最多只能比 $h=1$ 节省 $i-1$ 个空格，所以 $w=\lfloor\frac{L}{i}\rfloor-1$ 是不可能成立的。

所以 $h=i$ 且更优秀时的 $w$ 一定为 $\lfloor\frac{L}{i}\rfloor$。

那么求出 $L$ 之后枚举 $h$ 即可。