HDU_5802

描述

一个神奇的调节音量的事件。向上只能一次加一，向下调节的幅度是上一秒向下调节的两倍，若上一秒没有向下调节，那么幅度为一。从p到q，问最少的操作数。

题解

官方题解:

您可能是正版Windows 10的受害者 直接贪心就好
比较直观的看法是使劲往下降，然后升回来
或者使劲往下降然后停顿然后再使劲往下降。。。
于是就能将问题变成一个子问题，然后dfs就好
需要注意的是由于按up键也可以打断连续向下的功效
所以应该记录停顿了几次，以后向上的时候用停顿补回来

思路

但需要停顿的步数，和最后走过头向上调的步数是可以相互抵消的。两者取最大值。
首先，在没有低于目标值的时候，能向下走就向下走，贪心。
当走完这一步后为tmp=max(p,0),低于目标值q，那么进行讨论。
更新ans = min(ans,max(q-tmp,stay)+step);stay为停顿次数，step为当前步数
最后撤销当前步骤，返回上一步，采取停顿的策略，继续循环。
最后q-tmp<stay时可以得出答案ans = min(ans,step+stay);

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <complex>
#include <cstdio>
using namespace std;
#define ll long long
int main(){
    int T;
    cin>>T;
    while(T--){
        int p,q;
        scanf("%d%d",&p,&q);
        if(p<=q)printf("%d\n",q-p);
        else{
            int step=0,stay=0,ans=1e9,down=1;
            while(p>q){
                p-=down;
                down=down*2;
                step++;
                if(p<=q){
                    if(q-p<=stay){
                        ans = min(ans,step+stay);
                        break;
                    }
                    else{
                        ans = min(ans,max(q-max(p,0),stay)+step);
                        stay++;
                        step--;
                        down/=2;
                        p+=down;
                        down=1;
                    }
                }
            }
            printf("%d\n",ans);
        }
    }
    return 0;
}