做过好几道类似的题了,跟之前杭电的一道题很像。
反正就是在一个y的位置上下抖一抖再除2就行。
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<map>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define A puts("YES")
#define B puts("NO")
using namespace std;
typedef long long ll;
const ll inf=1ll<<60;
ll deep,n;
map<ll,ll> f;
map<ll,bool> bz;
void dfs(ll y){
if (y<=n) {
f[y]=n-y;
return;
}
if (y==2) {
f[2]=1;
return;
}
if (f.find(y)!=f.end()) return;
if (y%2==0) {
dfs(y/2);
dfs(y/2+1);
dfs(y/2-1);
f[y]=min(min(y-n,f[y/2]+1),2+min(f[y/2+1],f[y/2-1]));
}
else {
dfs(y/2);
dfs(y/2+1);
f[y]=min(min(f[y/2],f[y/2+1])+2, y-n);
}
}
int main(){
// freopen("data.in","r",stdin);
ll x,y;
scanf("%lld %lld",&x,&y);
n=x;
f[x]=0;
if (x>y) {
printf("%lld",x-y);
return 0;
}
dfs(y);
printf("%lld",f[y]);
return 0;
}
标签:abc188F,dfs,1x2,include,ll,define
From: https://www.cnblogs.com/ganking/p/17719158.html