1 条题解
-
0
根据题目要求,我们需要在至多 次查询内确定未知的宽度参数 ()。
每次查询可以输入一篇文章(一个正整数序列),系统返回显示所需行数(若无法显示则返回 )。
第一步:第一次查询 —— 确定 的大致范围
第一次查询输入 个 :
文章序列:
(共 个)- 由于每个单词长度 ,所以只要 ,编辑器一定能显示(不会出现无法显示的情况)。
- 显示时,每一行能放 个 ,所以:$$\text{所需行数} = \left\lceil \frac{10^5}{W} \right\rceil $$
设返回的行数为 ,则:
由此可以反推出 的范围:
$$\frac{10^5}{W} \le r_1 \quad \Rightarrow \quad W \ge \frac{10^5}{r_1} $$且
$$\frac{10^5}{W} > r_1 - 1 \quad \Rightarrow \quad W < \frac{10^5}{r_1 - 1} $$取整后:
$$W \in \left[ \left\lceil \frac{10^5}{r_1} \right\rceil ,\; \left\lceil \frac{10^5}{r_1 - 1} \right\rceil - 1 \right] $$注意当 时,,结合 得 ,直接结束。
举例
- …
观察发现:
对于每个可能的 ,区间长度 满足 。
这意味着区间内任意两个数的和至少大于 ,这是下一步构造的关键。
第二步:第二次查询 —— 精确定位
设第一次查询得到的区间为 ,其中:
$$L = \left\lceil \frac{10^5}{r_1} \right\rceil,\quad R = \left\lceil \frac{10^5}{r_1 - 1} \right\rceil - 1 $$我们知道 恒成立。
第二次查询构造如下文章:
- 对于 ,依次放入两个单词:
第一个单词长度 ,第二个单词长度 。
即文章序列为:
总长度 (由区间长度保证)。
分析显示过程
考虑第 组 :
- 如果 ,那么这两个单词可以放在同一行(因为当前行已有一个 ,加上 后不超过 )。
- 如果 ,则它们必须分成两行(第一个单词 在一行末尾,第二个单词 换到新行)。
注意 意味着 。
由于 ,所以 时确实会换行。
计算总行数
- 对于 :每组 占 行(两个单词在同一行)。
- 对于 :每组占 行(第一个单词单独一行,第二个单词另起一行)。
另外注意每组开始时,上一组的最后一个单词结束后,当前组的第一个单词 是否会与上一组末尾连续?
仔细模拟:
每组是 ,上一组的末尾单词是 ,当前组的第一个单词 。
因为 吗?不一定,但本题的关键是跨组衔接不影响总行数计算,因为我们在统计总行数时,可以按“每组的单词对”独立分析,而跨组时由于 较大,实际上每组第一个单词 必定在新行开始(除了第一组)。
但为了严谨,官方解法利用 保证每组内部是独立判断是否换行,且组间自动换行。不过简单结论:
总行数化简:
因此:
第三步:输出答案
我们已知 (从第一次查询得到),(第二次查询返回的行数),直接计算 并输出:
! W
复杂度与正确性
- 第一次查询:,合法。
- 第二次查询:,合法。
- 总查询次数:,符合题目要求。
- 公式推导依赖 保证每组内部判断有效。
总结
步骤 操作 得到信息 1 输入 个 ,得区间 2 输入 ,解出 3 输出 答案正确 这就是本题 Easy Version 的标准解法。
- 1
信息
- ID
- 6443
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 8
- 标签
- 递交数
- 2
- 已通过
- 0
- 上传者