Searching for Soulmates (USACO Silver 2022 January)

这个题我们首先寻找有没有公式化的最优策略，直接对着操作就一定是最优的这种，找了一段时间发现似乎没有的。

退而求其次，我们找相对最优，但是还是需要做一些搜索的策略：

首先不断对 $x$ 进行除以 $2$ 操作，直到 $x$ 小于 $y$ 的某个前缀（如果中间需要可以做加 $1$ 操作使得数字变成偶数）。
然后通过加 $1$ 操作使 $x$ 等于该前缀。
接着不断对 $x$ 乘以 $2$ ，并在中间需要时加 $1$ ，直到 $x = y$ 。

这里不确定的变量就是前缀的长度，我们对于所有可能的 $y$ 的前缀都进行搜索，这样就可以找到最优解了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int t;
long long x0, x, y;
long long ans;
 
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%lld %lld", &x0, &y);
        ans = 1e9;
        for (int shift = 0; y >> shift > 0; shift++) {
            long long r = 0;
            x = x0;
            long long prefix = y >> shift;
            // reduce x to prefix
            while (x > prefix) {
                if (x % 2 == 0) {
                    x /= 2;
                    r++;
                } else {
                    x += 1;
                    r++;
                }
            }
            // add back to prefix
            if (x < prefix) {
                r += prefix - x;
                x = prefix;
            }
            // multiply and add 1 until x == y
            int s = shift;
            while (x < y) {
                x *= 2;
                r++;
                s--;
                if (y >> s > x) {
                    x += 1;
                    r++;
                }
            }
            ans = min(ans, r);
        }
        printf("%lld\n", ans);
    }
 
    return 0;
}