C++(clang++11) 解法, 执行用时: 44ms, 内存消耗: 48864K, 提交时间: 2021-04-24 14:48:56

#include <cstdio>
#include <algorithm>

using namespace std;

bool b[500000][20];
int gx[10000000],gy[10000000],gz[10000000],h[10000000];
int x,y,z,H,T;

int main()
{
	scanf("%d%d",&x,&y);
	T=1,gx[T]=y-x,gy[T]=0,gz[T]=-1,h[T]=0,b[250000+gx[T]][gy[T]]=true;
	for (H=1;H<=T;H++)
	{
		if (! gx[H])
		{
			printf("%d",h[H]);
			return 0;
		}
		x=gx[H],y=gy[H],z=gz[H];
		if ((abs(x+(1<<y)*z)<=150000) && (! b[250000+x+(1<<y)*z][y+1]))
			T++,gx[T]=x+(1<<y)*z,gy[T]=y+1,gz[T]=-z,h[T]=h[H]+1,b[250000+gx[T]][gy[T]]=true;
		if (! b[250000+x][0])
			T++,gx[T]=x,gy[T]=0,gz[T]=-1,h[T]=h[H]+1,b[250000+gx[T]][gy[T]]=true;
	}
}

Python3(3.9) 解法, 执行用时: 1132ms, 内存消耗: 11036K, 提交时间: 2021-04-27 19:02:29

s, t = map(int, input().split())
ma = {0: 0, 1: 1}
tmp, op, M = 0, 1, 40000
while abs(tmp) < M:
    ma[tmp + op] = ma[tmp] + 1
    tmp += op
    op *= -2
dp = {i: float('inf') for i in range(-M, M)}
for x in ma:
    dp[x] = ma[x]
for x in ma:
    for y in range(-M, M):
        if y - x in dp:
            dp[y] = min(dp[y], dp[y - x] + ma[x] + 1)
print(dp[t - s])
# mstdy dalao tql