题意
你有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; }