P8481 Binary search 题解

JackMerryYoung · 2022-08-20 20:51:19 · 题解

前言

月赛 T2, 纯暴力可还行。

正文

第一眼我们想到的应该是贪心，每次尽可能使得区间最小，但是手模几组数据就发现是错的。可是为什么错了？

因为你前面的决策缩小长度的可能小于后面的决策缩小长度的可能，而前面的决策影响后面的决策，显然不正确。

那么再回头看看题面。看一眼数据范围发现 \mathcal{O}(NQ) 做法竟然能过，于是直接上 DFS 暴搜：

先抄出题人的板子，然后直接枚举 w, 把题目里面的 w 设置为 0, 1, 都分别去跑一遍二分。

这样递归下去，当二分查找到要求的数时，结束，将递归层数取个最小值。

最终的最小值就是我们的答案了。注意第一层 DFS 的层数是 0 啊！

理论上是 \mathcal{O}(NQ) 的，应该可以通过（可见你谷评测机有多强）。

代码

伪代码：

Func binary_search(num[], x, l, r, step):
    If(l == r):
        ans = min(ans, step)
        Ret None

    mid = (l + r) / 2;
    If(num[mid] < x):
        binary_search(num[], x, mid + 1, r, step + 1)
    Else:
        binary_search(num[], x, l, mid, step + 1)

    mid = (l + r + 1) / 2;
    If(num[mid] - 1 < x):
        binary_search(num[], x, mid, r, step + 1)
    Else:
        binary_search(num[], x, l, mid - 1, step + 1)

... <- Input

For Each Query:
    x = read()
    ans = INF
    binary_search(arr[], x, 0, N - 1, 0)
    Write(ans)

后言

这种题目就先交个暴力试试，实在不行再考虑正解。