题解 CF11B 【Jumping Jack】
珅肐
·
·
题解
更优的做法！
其实O(\sqrt x)已经足够了，其他两篇题解就是O(\sqrt x)模拟了跳的步数
那两篇讲的已经够好了，这里只简单说一下
我们一次一次向右跳，直到刚好跳到或跳过
刚好跳到即最优解，
否则，我们设当前跳到y
如果y-x为偶数，可以将第\frac{(y-x)}2步往左跳，步数减少了\frac{(y-x)}2*2，可以恰好跳到x.
如果y-x为奇数，那么继续跳
但是，我们还有更优的算法
我们二分跳的步数l，直到跳到或跳过x
然后按上面步骤进行
复杂度O(log\sqrt x)
又：
如果y-x为奇数
$2.$ 二分到的$l$是偶数，还需要跳一次
最多需要两次
### 代码奉上：
```cpp
#include<iostream>
#include<cstdio>
#include<ctype.h>
#include<cmath>
using namespace std;
inline int read(){//快读，可快了，虽然这道题没什么用
int x=0;char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))x=x*10+(ch^48),ch=getchar();
return x;
}
int main(){
int x=read(),ans=0,l=0,r=sqrt(x+x)+1;//二分边界设到平方刚好大于x即可
while(l<=r){
int m=l+r>>1;
if(m*(m+1)/2<x)l=m+1;
else r=m-1;
}//普通二分
if((l*(l+1)/2-x)&1)++l;
if((l*(l+1)/2-x)&1)++l;//最多进行两次
printf("%d\n",l);
return 0;//好习惯
}
```