链接：https://ac.nowcoder.com/acm/contest/331/D
来源：牛客网
 

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

小希现在要从寝室赶到机房，路途可以按距离分为N段，第i个和i+1个是直接相连的，只需要一秒钟就可以相互到达。

炫酷的是，从第i个到第i+2^p个也是直接相连的（其中p为任意非负整数），只需要一秒钟就可以相互到达。

更炫酷的是，有K个传送法阵使得某些u,v之间也是直接相连的，只需要一秒钟就可以相互到达，当然，由于设备故障，可能会有一些u=v的情况发生。

现在小希为了赶路，她需要在最短的时间里从寝室(编号为1)到达机房(编号为N)，她不希望到达这N个部分以外的地方（不能到达位置N+1），也不能走到比自己当前位置编号小的地方（比如从5走到3是非法的）。

她想知道最短的时间是多少。

输入描述:

第一行输入两个整数N,K，表示路途的段数和传送法阵的数量。

从第二行开始K行，每行两个整数ai,bi表示两个位置之间相连。
2≤N≤1,000,000,000

0≤K≤15

输出描述:

输出一个整数，表示从寝室到机房最短的时间是多少秒。

示例1

输入

复制

12 2
1 5
6 6

输出

复制

3

示例2

输入

复制

17 2
2 5
8 9

输出

复制

1

3种走法：我定义为：1.一次一次走法                        2. 2^p走法                               3.  传送走法   

题意：不解释~

题解：贪心想一下，每次走2^p次肯定比一次一次走法快，然后就用2^p走法 与 传送加2^p走法进行比较，就可以啦，而且这种走法还可以贪心，就是一次走一步最大的，然后走小的~~~至于为啥可以~我就说：贪心贪心~~上代码：
 

#include <iostream>
using namespace std;
typedef long long ll;
const int MAX = 31;
ll a[MAX];
void init(){
    a[0]=1;
    for (int i = 1; i <= 30;i++){//二的多少次方，1e9就到30了
        a[i]=a[i-1]*2;
    }
}
ll zhao(ll u,ll v){
    ll sum=0;
    while(u<v){
        for (int i = 30; i >= 0;i--){//贪心，从大步到小步
            if(u+a[i]<=v){
                u+=a[i];
                sum++;
                break;
            }
        }
    }
    return sum;
}
int main(){
    init();
    ll n,k;
    cin >> n >> k;
    ll ans;
    ans=zhao(1,n);//纯2^p走法
    for (int i = 0; i < k;i++){
        int u,v;
        cin >> u >> v;
        if(u>v) swap(u,v);
        if(u==v) continue;
        ans=min(ans,zhao(1,u)+1+zhao(v,n));//传送走法+2^p走法，与 纯2^p走法求最小值
    }
    cout << ans << endl;
    return 0;
}