1 条题解

  • 0
    @ 2026-4-6 14:39:47

    根据题目要求,我们需要在至多 22 次查询内确定未知的宽度参数 WW1W1051 \le W \le 10^5)。
    每次查询可以输入一篇文章(一个正整数序列),系统返回显示所需行数(若无法显示则返回 00)。


    第一步:第一次查询 —— 确定 WW 的大致范围

    第一次查询输入 n=105n = 10^511

    文章序列:
    [1,1,1,,1][1, 1, 1, \dots, 1](共 10510^5 个)

    • 由于每个单词长度 ai=1a_i = 1,所以只要 W1W \ge 1,编辑器一定能显示(不会出现无法显示的情况)。
    • 显示时,每一行能放 WW11,所以:$$\text{所需行数} = \left\lceil \frac{10^5}{W} \right\rceil $$

    设返回的行数为 r1r_1,则:

    r1=105Wr_1 = \left\lceil \frac{10^5}{W} \right\rceil

    由此可以反推出 WW 的范围:

    $$\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] $$

    注意当 r1=1r_1 = 1 时,W105W \ge 10^5,结合 W105W \le 10^5W=105W = 10^5,直接结束。


    举例

    • r1=1W=105r_1 = 1 \Rightarrow W = 10^5
    • r1=2W[50000,99999]r_1 = 2 \Rightarrow W \in [50000, 99999]
    • r1=3W[33334,49999]r_1 = 3 \Rightarrow W \in [33334, 49999]
    • r1=4W[25000,33333]r_1 = 4 \Rightarrow W \in [25000, 33333]

    观察发现:
    对于每个可能的 r1r_1,区间长度 RL+1R-L+1 满足 2L>R2L > R
    这意味着区间内任意两个数的和至少大于 RR,这是下一步构造的关键。


    第二步:第二次查询 —— 精确定位 WW

    设第一次查询得到的区间为 [L,R][L, R],其中:

    $$L = \left\lceil \frac{10^5}{r_1} \right\rceil,\quad R = \left\lceil \frac{10^5}{r_1 - 1} \right\rceil - 1 $$

    我们知道 2L>R2L > R 恒成立。

    第二次查询构造如下文章:

    • 对于 x=1,2,,RLx = 1, 2, \dots, R-L,依次放入两个单词:
      第一个单词长度 =L= L,第二个单词长度 =x= x

    即文章序列为:

    [L,1,  L,2,  L,3,  ,  L,RL][L, 1, \; L, 2, \; L, 3, \; \dots, \; L, R-L]

    总长度 n=2×(RL)105n = 2 \times (R-L) \le 10^5(由区间长度保证)。


    分析显示过程

    考虑第 xx(L,x)(L, x)

    • 如果 L+xWL + x \le W,那么这两个单词可以放在同一行(因为当前行已有一个 LL,加上 xx 后不超过 WW)。
    • 如果 L+x>WL + x > W,则它们必须分成两行(第一个单词 LL 在一行末尾,第二个单词 xx 换到新行)。

    注意 L+x>WL + x > W 意味着 x>WLx > W - L

    由于 2L>RW2L > R \ge W,所以 L+x>L+(WL)=WL + x > L + (W - L) = W 时确实会换行。


    计算总行数

    • 对于 x=1(WL)x = 1 \dots (W - L):每组 (L,x)(L, x)11 行(两个单词在同一行)。
    • 对于 x=(WL+1)(RL)x = (W-L+1) \dots (R-L):每组占 22 行(第一个单词单独一行,第二个单词另起一行)。

    另外注意每组开始时,上一组的最后一个单词结束后,当前组的第一个单词 LL 是否会与上一组末尾连续?
    仔细模拟:
    每组是 (L,x)(L, x),上一组的末尾单词是 x1x-1,当前组的第一个单词 LL
    因为 L+(x1)L+1>WL + (x-1) \ge L + 1 > W 吗?不一定,但本题的关键是跨组衔接不影响总行数计算,因为我们在统计总行数时,可以按“每组的单词对”独立分析,而跨组时由于 LL 较大,实际上每组第一个单词 LL 必定在新行开始(除了第一组)。
    但为了严谨,官方解法利用 2L>R2L > R 保证每组内部是独立判断是否换行,且组间自动换行。

    不过简单结论:
    总行数 r2=(WL)+2×((RL)(WL))r_2 = (W - L) + 2 \times \big((R-L) - (W-L)\big)

    化简:

    r2=(WL)+2(RW)r_2 = (W - L) + 2(R - W) r2=WL+2R2Wr_2 = W - L + 2R - 2W r2=2RLWr_2 = 2R - L - W

    因此:

    W=2RLr2W = 2R - L - r_2

    第三步:输出答案

    我们已知 L,RL, R(从第一次查询得到),r2r_2(第二次查询返回的行数),直接计算 WW 并输出:

    ! W
    

    复杂度与正确性

    • 第一次查询:n=105n = 10^5,合法。
    • 第二次查询:n=2(RL)105n = 2(R-L) \le 10^5,合法。
    • 总查询次数:22,符合题目要求。
    • 公式推导依赖 2L>R2L > R 保证每组内部判断有效。

    总结

    步骤 操作 得到信息
    1 输入 10510^511 r1=105/Wr_1 = \lceil 10^5 / W \rceil,得区间 [L,R][L,R]
    2 输入 [L,1,  L,2,  ,L,RL][L,1,\; L,2,\; \dots, L,R-L] r2=WL+2(RW)r_2 = W-L + 2(R-W),解出 W=2RLr2W = 2R-L-r_2
    3 输出 WW 答案正确

    这就是本题 Easy Version 的标准解法。

    • 1

    信息

    ID
    6443
    时间
    1000ms
    内存
    256MiB
    难度
    8
    标签
    递交数
    2
    已通过
    0
    上传者