题目描述

最近米咔买了$n$ 个苹果和 $m$ 个香蕉，他每天可以选择吃掉一个苹果和一个香蕉（必须都吃一个，即如果其中一种水果的数量为 $0$，则他不能进行这个操作），或者使用魔法将某一种水果的数量翻倍。

现在米咔想吃西瓜了，但是他的主人赛小息不让他买新水果，除非苹果和香蕉没有了，即数量都是 $0$ 了。

现在米咔想知道，最少用多少天他可以吃光苹果和香蕉。

可以证明的是，一定存在一种方案可以让米咔在若干天后吃光苹果和香蕉。

输入格式

第一行一个正整数 $T(T\le 100)$，代表数据组数。

接下来 $T$ 行每行两个正整数 $n，m(n，m\le 100000)$。

输出格式

共 $T$ 行，每行一个正整数代表答案。

样例输入

3
1 1
1 2
2 5

样例输出

1
3
7

提交链接

吃水果

提示

对于第三组测试样例$（2,5）$，第一天令 $n$ 翻倍变成$（4,5）$，接下来连续吃三天水果变成$（1,2）$，第五天令 $n$ 翻倍变成$（2,2）$，接下来连续吃两天水果，在第七天时吃光苹果和香蕉。

解析

💡关键观察点是：

• 每次吃水果操作减少 $(1,1)$，所以最终苹果和香蕉数量必须相等才能吃光。

• 你可以通过对某一边翻倍，使两者变得相等（或接近），然后吃掉。

✨ 主要策略
我们想办法让两个数尽量相等且尽量大，然后每天消耗 $(1,1)$。每次操作要么吃掉一对水果，要么对少的那个翻倍，让它追上多的那个。

参考代码

#include <bits/stdc++.h>
using namespace std;int main()
{int t, n, m;cin >> t;   //t组样例while (t--){cin >> n >> m;int cnt = 0;  //统计答案if(n > m)swap(n , m);while(n != m){if(n * 2 <= m)     //小的那个可以翻倍n *= 2 , cnt++;elsen-- , m-- , cnt++;     //当前这一天吃(1,1)}cnt += n;   //跳出while循环的条件为n==m，最终吃n天全部减小到0cout << cnt << endl;}return 0;
}