hdu 5802 Windows 10 贪贪贪

时间：2022-08-11 11:53:36

传送门：hdu 5802 Windows 10

题意：把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\n",a)

#define ptlld(a) printf("%I64d\n",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=*atan(1.0);

using namespace std;

typedef long long ll;

template <class T> inline void read(T &n)

{

    char c; int flag = ;

    for (c = getchar(); !(c >= '' && c <= '' || c == '-'); c = getchar()); if (c == '-') flag = -, n = ; else n = c - '';

    for (c = getchar(); c >= '' && c <= ''; c = getchar()) n = n *  + c - ''; n *= flag;

}

int Pow(int base, ll n, int mo)

{

    if (n == ) return ;

    if (n == ) return base % mo;

    int tmp = Pow(base, n >> , mo);

    tmp = (ll)tmp * tmp % mo;

    if (n & ) tmp = (ll)tmp * base % mo;

    return tmp;

}

//***************************

ll p,q;

const int maxn=+;

ll bit[];

void init()

{

    bit[]=;

    for(int i=;i<=;i++)

        bit[i]=bit[i-]<<;

    for(int i=;i<=;i++)

        bit[i]-=;

}

ll ans;

int tot;

void dfs(int temp,int nn)//temp保存的是p和q的差值

{

    if(temp==)

    {

        ans=Min(ans,nn);

        return;

    }

    int res=nn;

    int tt=lower_bound(bit,bit+,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+=,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=;kase<=T_T;kase++)

    {

        sclld(p);

        sclld(q);

        if(p<=q)

        {

            printf("%I64d\n",q-p);

            continue;

        }

        ll temp=p-q;

        ans=oo;

        tot=;

        dfs(temp,);

        ptlld(ans);

    }

}

相关文章