专栏文章

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

2025/01/11 16:12题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论: 0 条
当前快照: 1 份
快照标识符: @miqjj81k
此快照首次捕获于: 2025/12/04 05:50
此快照最后确认于: 2025/12/04 05:50

~~好臭的样例~~

做法

本蒟蒻的第一个想法：

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

本蒟蒻的第二个想法：

发现变量

a

一定会先不断乘

2

，再由变量

b

加（减）得来，然而我们很容易想到这题需要分两个情况，如下：

$a$ 不断乘 $2$ 直至比 $b$ 大，再由 $b$ 不断加 $1$ 得来。
$a$ 不断乘 $2$ 直至再乘一次就会比 $b$ 大，再由 $b$ 不断减 $1$ 得来。

代码

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

CPP

#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...