刷题刷出新高度,偷偷领先!偷偷领先!偷偷领先! 关注我们,悄悄成为最优秀的自己!

简答题

方块城堡

编程实现

为了迎接新同学,学校用方块打算在校门口堆一座城堡,让同学们拍照打卡。老师标记了 n 个位置,这些位置从左到右排成一整排,编号从 1 到 n。他原本打算在第 i 号位置用 ai个方块搭建城堡的某种结构。然而,送货的司机过于粗心,胡乱地把方块卸下后就离开了。老师统计了一下,发现目前在第 i 号位置的方块数量是 bi(司机把所有方块都卸下了,所以 ai 之和等于 bi之和)。

无奈之下,老师只能让同学们帮忙移动这些方块,由于方块很重,所以一次只能把一个方块移动到相邻编号的位置上。请帮同学们规划一下,要最少移动多少次才能让所有位置的方块数量从bi 变成 ai。

输入描述

输入共三行。

第一行一个正整数 n,表示位置个数。(1≤n≤1000)

第二行 n 个正整数 ai,表示原本计划中每个位置的方块个数。

第三行 n 个正整数 bi,表示目前每个位置的方块个数。(1≤ai,bi≤1000)

输出描述

输出一行一个数字,表示最少需要的移动次数。


输入样例

5
1 2 3 4 5
3 1 2 5 4

输出样例

4

使用微信搜索喵呜刷题,轻松应对考试!

答案:

2

解析:

【喵呜刷题小喵解析】:本题需要找到最少移动次数使得所有位置的方块数量从bi变为ai。一种可行的思路是:从左到右遍历每个位置,如果当前位置的方块数量bi大于ai,则需要进行移动。每次移动可以选择将多余的方块移动到相邻的右侧位置,或者将相邻的左侧位置的方块移动到当前位置。通过贪心算法,我们可以选择使得移动次数最少的方式。

对于输入样例,我们可以按照以下步骤进行:

1. 遍历每个位置,如果bi > ai,则需要进行移动。
2. 对于需要移动的位置,如果右侧相邻位置为空或者方块数量小于等于ai,则将多余的方块移动到右侧相邻位置。
3. 如果右侧相邻位置已经有方块,且方块数量大于ai,则无法将多余的方块移动到右侧相邻位置,此时需要将相邻的左侧位置的方块移动到当前位置。

对于输入样例,需要进行移动的位置有第2个位置(3>1)、第4个位置(5>2)。在第2个位置,多余的方块数量为3-1=2,右侧相邻位置为空,所以将多余的方块移动到右侧相邻位置即可。在第4个位置,多余的方块数量为5-2=3,右侧相邻位置已经有方块,且方块数量小于等于ai,所以将多余的方块移动到右侧相邻位置即可。总共需要进行2次移动,所以最少需要的移动次数为2。
创作类型:
原创

本文链接:方块城堡 编程实现 为了迎接新同学,学校用方块打算在校门口堆一座城堡,让同学们拍照打卡。老师标记了

版权声明:本站点所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。

让学习像火箭一样快速,微信扫码,获取考试解析、体验刷题服务,开启你的学习加速器!

分享考题
share