題目描述

最近米咔買了$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;
}