CF11B Jumping Jack

Loner_Knowledge · 2018-02-05 15:34:39 · 题解

这是一道数学题

题意是求到达x的最少跳跃次数。首先由于对称，x与是-x是等效的，因此均把负数看做正数。设最少跳跃次数为n，那么可以得到一个结果d=(\pm1)+(\pm2)+...+(\pm n)。

最快的跳法是往一个方向一直跳。如果恰好能到x，这样肯定是跳跃次数最小。如果不能恰好跳到，那么我们设y为以这种跳法得到的第一个比x大的点，如果y-x为偶数，可以将第(y-x)/2步往左跳，这样就能恰好跳到x了；如果y-x为奇数，那么继续跳直到与x的差为偶数即可。

#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)   //i为跳跃次数，t为累计跳跃的距离
        if(t==x||(t>x&&!((t-x)%2)))
            ans=i;                      //符合分析中的条件便跳出循环
    printf("%d",ans);
    return 0;
}