CF1672E notepad.exe 做题记录

这是一道交互题。

在文本编辑器里有 nn 个单词,其中第 ii 个单词的长度为 lil_i (1li20001 \le l_i \le 2000)。ll 仅对测评机可见。

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

更正式地,设文本编辑器的宽度为 ww 。设 aa 是一个长度为 k+1k + 1 的序列,其中 1=a1<a2<...<ak+1=n+11 = a_1 < a_2 < ... < a_{k+1} = n + 1. {an}\{a_n\} 是一个合法的序列当且仅当,1ik,lai+1+lai+1+1++1+lai+11w\forall 1 \le i \le k, l_{a_i} + 1 + l_{a_{i + 1}} + 1 + \dots + 1 + l_{a_{i+1} - 1} \le w。 那么,hh 就是所有合法的 {an}\{a_n\} 中最小的 kk.。

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

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

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

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

考虑 3030 次操作能求出什么,显然可以二分求出:

  1. 最长的单词长度 mxlenmxlen
  2. h=1h=1 时最小的 ww,即所有单词的长度和加上 n1n-1,设它为 LL

mxlenmxlen 好像没什么用,那么考虑 LL 的用途。

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

所以 h=ih=i 且更优秀时的 ww 一定为 Li\lfloor\frac{L}{i}\rfloor

那么求出 LL 之后枚举 hh 即可。