P8093 [USACO22JAN] Searching for Soulmates S

题目描述

Farmer John 的每头奶牛都想找到她们的灵魂伴侣——另一头具有相似特点的奶牛，与她们最大程度地相容。每头奶牛的性格由一个整数 $p_i$（$1\le p_i\le 10^{18}$）描述。两头性格相同的奶牛就是灵魂伴侣。奶牛可以通过「改变操作」，对她的性格乘以 $2$，除以 $2$（当 $p_i$ 是偶数时），或者加上 $1$。

Farmer John 最初以任意方式配对了他的奶牛。他很好奇为使每对奶牛成为灵魂伴侣需要进行多少次改变操作。对于每对奶牛，求配对中的第一头奶牛所必须进行的最小改变操作次数，从而可以与第二头奶牛成为灵魂伴侣。

输入格式

输入的第一行包含 $N$（$1\le N\le 10$），为奶牛配对的数量。以下 $N$ 行每行描述了一对奶牛，包含两个整数，为她们的性格值。第一个整数是需要被改变与另一头奶牛相匹配的奶牛的性格。

输出格式

输出 $N$ 行。对于每一对奶牛，输出第一头奶牛需要进行的最小操作次数，使得她的性格与第二头奶牛相匹配。

输入输出样例 #1

输入 #1

6
31 13
12 8
25 6
10 24
1 1
997 120

输出 #1

8
3
8
3
0
20

说明/提示

【样例解释】

对于第一个子测试用例，一个最优的操作序列为 $31⟹32⟹16⟹8⟹9⟹10⟹11⟹12⟹13$。

对于第二个子测试用例，一个最优的操作序列为 $12⟹6⟹7⟹8$.

【数据范围】

• 测试点 1-4 满足 $p_i\le 10^5$。
• 测试点 5-12 没有额外限制。

C++实现

#include <bits/stdc++.h>
using namespace std;
long long n;
long long len(long long num) {
  for (long long i = 63; i >= 0; i--) {
    if ((num >> i) & 1) {
      return i + 1;
    }
  }
  return 0;
}
long long get(long long num, long long i, long long len) {
  return num >> (len - i);
}
void solve() {
  long long a, b, c, cnt = 0, ans = INT_MAX;
  cin >> a >> b;
  if (a == b) {
    cout << 0 << endl;
    return;
  }
  c = len(b);
  long long save = a;
  for (long long i = 1; i <= c; i++, ans = min(ans, cnt), a = save) {
    cnt = 0;
    long long nowb = get(b, i, c);
    while (a != nowb) {
      if (a > nowb) {
        if (a & 1) a++;
        else a /= 2;
        cnt++;
      } else {
        cnt += nowb - a;
        a = nowb;
      }
    }
    for (long long j = i + 1; j <= c; j++) {
      nowb = get(b, j, c);
      a <<= 1;
      cnt++;
      if (nowb != a) a++, cnt++;
    }
  }
  cout << ans << endl;
}

int main() {
  cin >> n;
  while (n--) {
    solve();
  }
  return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容