牛客练习赛61 B吃水果(证明数学规律解）

吐槽，为什么大家都没有证明过程，我来写一个吧。
输入入有n个香蕉m个苹果；
因为要把两种水果要吃完，而且水果种类对解基本没有影响，所以，可以使n的数量最大，以方便之后的操作。
即if(n<m) swap(n,m);
核心思维就是:

• 设一个临时变量int tmp=n-m;
• 如果m大于tmp时，可以将m减为m=tmp，此时n=2*tmp；
• 此时将m翻倍，
• 就使得m==n;就获得了解，
• 也就是当m大于等于1/2n时，此时就可以获得解，
• 那么当m大于等于0.5n时会怎么样呢，此时就可以做第一次的操作
• tmp=n-m，使mn一起减少，使m=tmp，此时n=2*tmp；然后，m= m * 2，此时，m==n啦
• 那么翻倍的次数的规律你找到了么？
• 设翻倍的次数t=0，

  while(m<n/2) {//注意此时的n不能是int类型的，n是double类的，否则如果n=9，m等与1，就会少一次翻倍，当然程序里没有除法
  t++; m=m*2;}//这里的除法只是为了符合思维逻辑

  是m>=(0.5n)的次数+1；
  你看这个是不是有什么规律呢？
  对，此时m再翻倍一次的话，就会 m>=n
• 也就是说，翻倍的总次数就是使m>=n所需要的翻倍的总次数；*

而n始终没有增加过，只需要吃n个水果就可以啦；

• 第一步 先使(n>=m)
• 第二步 特判(n==m)//如果相等的话，直接输出结果为n就可以了，其实可以不必判断，划掉

  
  

• 第三步 判断使2*m>=n的次数 ，设为t次
• 第四步 输出t+n，这就是答案

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    int T;
    scanf("%d",&T);
    int n,m;
    int t=0;
    while(T--){
        t=0;
        scanf("%d %d",&n,&m);//输入水果的数量
        if(n<m) swap(n,m);//交换值，始终使n最大
        while(m<n){//判断需要乘的次数
            m=m*2;t++;
        }
        printf("%d\n",n+t);
    }
    return 0;
}

贴一下比赛的做法，当时没有这么优化，思维还是差了一层

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int T;
    scanf("%d",&T);
    int sum=0;//总天数
    int n,m;
    int ksp=0;
    while(T--){
        sum=0;
        scanf("%d %d",&n,&m);
        if(n==m){//特判
            printf("%d\n",n);
            continue;
        }
        while(n!=m){
        if(n<m) swap(n,m);
        ksp=n-m;//两数的差值
            if(m<ksp){
                m=m*2;
                sum++;
                continue;
            }
            if(m==ksp){
                m=m*2;
                sum++;
                sum=sum+m;
                break;
            }
            if(m>ksp){
                int tmp=(m-ksp);
                n=n-tmp;
                m=m-tmp;
                sum=sum+tmp;
            }
        }
        printf("%d\n",sum);//输出天数
    }
    return 0;
}

最后，求赞