CF11 B. Jumping Jack

Problem - 11B - Codeforces

 

题意:

坐标轴, 初始在0,目标位置x,第i步可以移动距离i,可以左移或者右移

问最少需要多少步

 

假设每一步都往目标方向去,就是问最小的t,满足1+2+3+……+t = t*(t+1)/2 >= x

如果恰好是x,那就结束了

如果大于x,那么就需要把前面的某些步反方向

假设现在的位置是y,把第i步反方向会使位置变为y-2*i

而1—t的任意步都可以反向

所以如果y-x是偶数,答案就是t

否则,说明y-x是奇数,那么如果t+1是奇数,答案是t+1,否则是t+2

 

#include<cstdio>

int main()
{
    int x,l,r,mid,tmp;
    scanf("%d",&x);
    if(x<0) x=-x;
    l=0;
    r=1e9;
    while(l<=r)
    {
        mid=l+r>>1;
        if(1ll*mid*(mid+1)/2>=x)
        {
            tmp=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    int now=1ll*tmp*(tmp+1)/2;
    if(!((now-x)&1)) printf("%d",tmp);
    else if(!(tmp&1)) printf("%d",tmp+1);
    else printf("%d",tmp+2); 
}

 

上一篇:【zyc的从零开始】20211011 java简介和一些变量类型


下一篇:linux用户不在sudoers文件中