题意
你有n个苹果和m个香蕉,你可以花一天时间使得其中一种水果翻倍,或者花一天时间同时吃掉1个苹果和1个香蕉,苹果和香蕉必须同时吃掉。
求最少多少天可以吃完?
思路
贪心:我们翻倍要做到既让水果得到最大程度的补充,又不能超过,则进行翻倍。
这里苹果和香蕉是等地位的,为了方便我们先把大的给到,小的给到
,
看了眼官方题解,是可以用数学公式优化到每次的,但是这题数据范围不大,直接这样模拟也能过。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
const ll maxn = 1e6 + 5;
ll n,m;
void solve(){
cin>>n>>m;
if(n<m) swap(n,m);
ll cnt=0;
for(;n>0||m>0;cnt++){
while(2*m<=n){
m=2*m;
cnt++;
}
n--;m--;
}
cout<<cnt<<'\n';
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int T; cin>>T;
while(T--){
solve();
}
return 0;
}
京公网安备 11010502036488号