算法提高课汇总

算法思路

边权为1, $bfs$求最短路问题.

注意扩展时数值的范围:

• 下界: 如果目标在当前位置左侧, 移动方式为$-1$, 因为$K\ge 0$, 所以下界为$0$.

• 上界: 如果目标在当前位置右侧, 移动方式为$+1$或$\times 2$, 因为$K\le 10^5$, 所以上界为$2\times 10^5$.
  (跳出$10^5$后不会再向右侧移动, 也就是最多$\times 2$一次).

具体代码

#include <iostream>

using namespace std;

const int N = 2e5 + 10;

int n, k;
int dist[N], q[N];

int bfs()
{
    int dx[] = {1, -1, 2};

    dist[n] = 1;
    int hh = 0, tt = 0;
    q[tt ++] = n;

    while( hh < tt )
    {
        int x = q[hh ++];

        if( x == k )    return dist[x] - 1;

        for( int i = 0; i < 3; i ++ )
        {
            int nx;
            if( dx[i] == 2 )    nx = x * dx[i];
            else    nx = x + dx[i]; 

            if( 0 <= nx && nx < N && !dist[nx] )
            {
                dist[nx] = dist[x] + 1;
                q[tt ++] = nx;
            }
        }
    }
    return -1;
}

int main()
{
    cin >> n >> k;

    cout << bfs() << endl;

    return 0;
}