题解：T549578 【MX-X7-T1】[LSOT-3] 分蛋糕

rq_hyj · 2025-01-11 16:12:38 · 题解

好臭的样例

做法

本蒟蒻的第一个想法：

使用 BFS 利用结构体记录两个变量和步数，但思考后发现好像会时空双爆（应该吧），所以想到了第二个方法。

本蒟蒻的第二个想法：

发现变量 a 一定会先不断乘 2，再由变量 b 加（减）得来，然而我们很容易想到这题需要分两个情况，如下：

代码

分类讨论还是相当简单的，只需仔细一点就能一遍过。

#include<cstdio>
#include<iostream>
using namespace std;
int n,m;
int cnt;
int main(){
    scanf("%d%d",&n,&m);
    if(n>m){
        printf("%d",n-m);
    }
    else{
        while(n<=m){
            n*=2;
            cnt++;
        }
        int a=n;
        int b=n/2;
        printf("%d",min(cnt+a-m,cnt-1+m-b));
    }
    return 0;
}