这是一道交互题。
在文本编辑器里有 n 个单词,其中第 i 个单词的长度为 li (1≤li≤2000)。l 仅对测评机可见。
文本编辑器一行一行展示文本,以空格分开相邻的两个单词,但是行末不一定有空格,即单词可以直接作为某一行的末尾。定义文本的高度 h 为文本展示需要的行数。对于给定的屏幕宽度,编辑器会以高度最小的方式显示。
更正式地,设文本编辑器的宽度为 w 。设 a 是一个长度为 k+1 的序列,其中 1=a1<a2<...<ak+1=n+1. {an} 是一个合法的序列当且仅当,∀1≤i≤k,lai+1+lai+1+1+⋯+1+lai+1−1≤w。 那么,h 就是所有合法的 {an} 中最小的 k.。
注意,如果 w≤max(li),那么文本编辑器将不能显示所有的文字并且崩溃,此时 h=0。
你可以做 n+30 次询问。每次询问中,输出宽度 w . 测评机将返回 hw ,即当宽度为 w 的最小高度。
请找到文本编辑器的最小面积,即求 min(w×hw∣1≤w≤n)。
看到 n+30 次询问,容易猜到应该是用 30 次操作求一个关于值域的东西,剩下 n 次操作求出答案。
考虑 30 次操作能求出什么,显然可以二分求出:
- 最长的单词长度 mxlen;
- h=1 时最小的 w,即所有单词的长度和加上 n−1,设它为 L。
mxlen 好像没什么用,那么考虑 L 的用途。
若 h=i 且此时更优秀,那么 w 的最大的情况只能是 ⌊iL⌋,并且由于 h=i 时最多只能比 h=1 节省 i−1 个空格,所以 w=⌊iL⌋−1 是不可能成立的。
所以 h=i 且更优秀时的 w 一定为 ⌊iL⌋。
那么求出 L 之后枚举 h 即可。