B3 猜数

提供一种乌七八糟的做法。。。

思路

正常的二分，当我们猜大了或猜小了缩小区间，直到我们猜到为止。

但是此题我的做法竟然非常玄学，大家待会看看代码。

解题方法

我是这么乱搞der：

首先，写出我的代码：

#include "guess.h"

int guess(int n) {
    int l = 1, r = n;

    while (true) {
        int mid = (l+r) / 2;
        int ques = ask(mid);

        if (ques == 0) {
            return mid;
        }

        if (ques == 1) {
            l = mid;
        } else {
            r = mid;
        }
    }
}

提交，发现只有 20 pts.

其中，WA的4个点都是猜多了1次。

怎么办？我们想到，中心点可能还有一个，既然总是猜多，那可能是我们运气不好。不如猜可能的另外一个中心点？

动手试试：

#include "guess.h"

int guess(int n) {
    int l = 1, r = n;

    while (true) {
        int mid = (l+r) / 2+1;
        int ques = ask(mid);

        if (ques == 0) {
            return mid;
        }

        if (ques == 1) {
            l = mid;
        } else {
            r = mid;
        }
    }
}

分数上升至 80 pts.

还有一个点，我们从测试反馈里看出正解是只猜0次的，不难想到可以在开头加个特判。

直接AC，具体看代码。

复杂度

时间复杂度:

$O(\text{log}_2n)$

空间复杂度:

$O(n)$

Code

#include "guess.h"

int guess(int n) {
    int l = 1, r = n;

    if (l == r) {
        return 1;
    }

    while (true) {
        int mid = (l+r) / 2+1;
        int ques = ask(mid);

        if (ques == 0) {
            return mid;
        }

        if (ques == 1) {
            l = mid;
        } else {
            r = mid;
        }
    }
}