官方题解｜勇敢的冒险者

题目大意

冒险者在一条 $x$ 轴上，并处于点 $0$，假设当前的位置是 $y$ ,现在正在进行第 $k$ 次跳跃,有两种跳跃的方案

• 向前跳跃到 $y+k$
• 向后跳跃到 $y-1$

冒险者要到达点 $x$ 点

题意分析

问最少跳跃几次，冒险者就能到达 $x$ 点

解题思路

由于一开始冒险者一定是在点 $0$ 的，并且 $x$ 点一定是大于 $0$ 的，很容易看出一开始只要一直执行 【方案一】 即 $y+k$ 就一定能到达 $\ge x$ 的位置。

如果执行了 $k$ 次后正好能到达 $x$ 点那么答案为 $k$

那如果超过了 $x$ 点呢? 这个时候我们需要考虑用 【方案二】 来进行干预了。

接下来我们分类讨论一下：

• 进行$k$次操作后，到达了 $x+1$ 的位置，那么我们只需要执行一次 【方案二】

• 进行$k$次操作后，到达了 $x+p$ 的位置，其中 $p$ $(p\gt 1)$ 为超出 $x$ 的部分

  这个时候可以有两种办法消除这个 $p$。

  第一种选择执行 $p$ 次 【方案二】

  第二种选择在之前跳跃的某次 【方案一】 将它改为 【方案二】

  显然这里选择 【方案二】 是最优的

所以我们只需要关心，经历几次 $k$ 能跳到 $\ge x$ 的点上就行了，这里可以使用二分去快速找到 $k$

时间复杂度解析

对于每个 $x$ 都需要进行一次二分即复杂度为：$O(\log_{2} n)$

代码演示

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll getSum(ll r) {
    return (1 + r) * r / 2;
}
int main() {
    int t,x;
    cin >> t;
    while(t--) {
        cin >> x;
        int l = 0,r = x;
        while(l <= r) {
            int mid = (l + r) >> 1;
            if (getSum(mid) >= x)r = mid - 1;
            else l = mid + 1;
        }
        ll s = getSum(l);
        if (s == x) {
            cout << l << endl;
        }else {
            if (s - 1 == x) {
                cout << l + 1 << endl;
            }else {
                cout << l << endl;
            }
        }
    }
    return 0;
}