题解 CF11B 【Jumping Jack】

Nepenthe · 2018-07-22 20:08:15 · 题解

首先产生的想法大概是向左k步后向右k+1步相当于向右1步,于是先尽量补齐到x再一步步跳.

然而肯定是错的.

正负等效性

无论x的正负实际上都不会影响跳的具体方案,所以x输入后取绝对值就好了,这样之后我们相当于只要向右跳

我们设最小跳的步数为n,则x=(\pm 1)+(\pm 2)+...(\pm n)

我们同样通过一直向右跳尽量逼近x,如果能刚好到x就直接输出.

如果不能,我们考虑把其中向右跳k步改为向左跳k步,那就会让我们最后的结果向左移2k步.

所以我们设y为跳得到的第一个比x大的点，然后

• 如果y-x为偶数，可以将第(y-x)/2步往左跳，这样就能恰好跳到x了.
• 如果y-x为奇数，那么继续跳直到与x的差为偶数即可。

Code

#include<cstdio>
int main() {
    int x,ans=0;
    scanf("%d",&x);
    if(x<0) x=-x;
    for(int i=1,t=1;x&&!ans;++i,t+=i)
        if(t==x||(t>x&&!((t-x)%2)))
            ans=i;
    printf("%d",ans);
    return 0;
}