题意：把p变成q；升的时候每次只能升1，降的时候如果前一次是升或者停，那么下一次降从1开始，否则为前一次的两倍
官方题解：
您可能是正版Windows 10的受害者_ 直接贪心就好
比较直观的看法是使劲往下降，然后升回来
或者使劲往下降然后停顿然后再使劲往下降。。。
于是就能将问题变成一个子问题，然后dfs就好
需要注意的是由于按up键也可以打断连续向下的功效
所以应该记录停顿了几次，以后向上的时候用停顿补回来
/************************************************************** Problem:hdu 5802 User: youmi Language: C++ Result: Accepted Time:312MS Memory:1580K ****************************************************************/ //#pragma comment(linker, "/STACK:1024000000,1024000000") //#include<bits/stdc++.h> #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <map> #include <stack> #include <set> #include <sstream> #include <cmath> #include <queue> #include <deque> #include <string> #include <vector> #define zeros(a) memset(a,0,sizeof(a)) #define ones(a) memset(a,-1,sizeof(a)) #define sc(a) scanf("%d",&a) #define sc2(a,b) scanf("%d%d",&a,&b) #define sc3(a,b,c) scanf("%d%d%d",&a,&b,&c) #define scs(a) scanf("%s",a) #define sclld(a) scanf("%I64d",&a) #define pt(a) printf("%d ",a) #define ptlld(a) printf("%I64d ",a) #define rep(i,from,to) for(int i=from;i<=to;i++) #define irep(i,to,from) for(int i=to;i>=from;i--) #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) #define lson (step<<1) #define rson (lson+1) #define eps 1e-6 #define oo 0x3fffffff #define TEST cout<<"*************************"<<endl const double pi=4*atan(1.0); using namespace std; typedef long long ll; template <class T> inline void read(T &n) { char c; int flag = 1; for (c = getchar(); !(c >= '0' && c <= '9' || c == '-'); c = getchar()); if (c == '-') flag = -1, n = 0; else n = c - '0'; for (c = getchar(); c >= '0' && c <= '9'; c = getchar()) n = n * 10 + c - '0'; n *= flag; } int Pow(int base, ll n, int mo) { if (n == 0) return 1; if (n == 1) return base % mo; int tmp = Pow(base, n >> 1, mo); tmp = (ll)tmp * tmp % mo; if (n & 1) tmp = (ll)tmp * base % mo; return tmp; } //*************************** ll p,q; const int maxn=200000+10; ll bit[40]; void init() { bit[0]=1; for(int i=1;i<=31;i++) bit[i]=bit[i-1]<<1; for(int i=0;i<=31;i++) bit[i]-=1; } ll ans; int tot; void dfs(int temp,int nn)//temp保存的是p和q的差值 { if(temp==0) { ans=Min(ans,nn); return; } int res=nn; int tt=lower_bound(bit,bit+31,temp)-bit;//求出连续降的次数,bit[tt]是大于等于temp的，所以如果取bit[tt]会得到小于0的结果，这时候只能升 if(tot>abs(bit[tt]-temp))//如果停顿的次数大于要升的大小，那么直接取0就好了 ans=Min(ans,nn+tt); else ans=Min(ans,nn+tt+Min(q,abs(bit[tt]-temp)-tot));//还有就是要和q比较，如果bit[tt]-temp>q，那么会减到小于0，而最小是0 if(temp<bit[tt])//如果取bit[tt-1]，也就是降到刚好比q大，这时候的操作就是减掉tt-1,然后停顿一下，并修改降了bit[tt-1]后的值 tt--; res+=tt; temp-=bit[tt]; if(temp)//tot表示停了几次 res+=1,tot++; dfs(temp,res); } int main() { #ifndef ONLINE_JUDGE freopen("in.txt","r",stdin); #endif init(); int T_T; scanf("%d",&T_T); for(int kase=1;kase<=T_T;kase++) { sclld(p); sclld(q); if(p<=q) { printf("%I64d ",q-p); continue; } ll temp=p-q; ans=oo; tot=0; dfs(temp,0); ptlld(ans); } }