1 条题解

  • 0
    @ 2026-11-15 12:30:22

    题解:木雕玩具(toy)

    不妨设 aa 单调递增(无重复),显然如果 n≤3n \leq 3,答案就是 00。

    显然答案 kk 具有可二分性。也就是说,当 k<k0k < k_0 时一定不存在合法的 x,y,zx, y, z,当 k≥k0k \geq k_0 时一定存在,k0k_0 就是答案。

    因此二分答案,只需要验证答案 kk 是否存在合法的 x,y,zx, y, z。

    为了覆盖到 a1a_1,且 xx 尽量往大取(这样可以覆盖更多的 aia_i),我们令 x=a1+kx = a_1 + k。接下来一段区间的 aia_i 会被 [x−k,x+k][x-k, x+k] 覆盖,我们跳过这段区间,找到下一个未被覆盖的 aia_i。类似于刚刚的思路,我们令 y=ai+ky = a_i + k,再找到下一个未被覆盖的 aja_j,令 z=aj+kz = a_j + k。如果此时所有 aia_i 都被覆盖了,那么就合法,否则不合法。

    时间复杂度 O(nlog⁡w)O(n \log w),其中 ww 为值域。

    • 1

    信息

    ID
    42
    时间
    1000ms
    内存
    256MiB
    难度
    4
    标签
    递交数
    1
    已通过
    1
    上传者