水库溃坝填补
2025华为OD机试双机位A卷 - 华为OD上机考试双机位A卷 100分题型
华为OD机试双机位A卷真题目录点击查看: 华为OD机试双机位A卷真题题库目录｜机考题库 + 算法考点详解
题目描述
一座水库在连续多日雨水的冲击下，发生了溃坝事故，解放军赶到现场救灾。其中，水坝两侧坝岩是坚固且高度相等，坝口用宽度为1的柱子的高度图表示，即一个非负整数数组-坝口数组。例如[7,3,0,0,7],其两侧坝岩高度是7，坝口数组则为[3,0,0],坝口面积为(7-4) + (7 - 0) + (7 - 0) = 18个单位。解放军手上有一批宽度为1，高度不一的木材，用一个非负整数数组- 木材数组表示，例如[4,7,4,3,3,5]可作为填补坝口的材料。解放军在指定溃口和填补木材以及工具约束情况下，使用最优填补策略让溃口面积变为最小，例如[4,7,5]，经填补木材后，原溃口[3,0,0]变为[7,7,5],溃口面积(7-7) + (7 - 7)+(7-5)=2个单位，为最小面积，则输出为填补木材的总高度: 4 + 7 + 5 = 16.
注意：
由于现场工具缺乏，每个宽度为1的溃口只能填补1根木材，每根木材只能整体填补，无法锯断。填补方案优先考虑将溃口填补到最小，若溃口填补效果一样，即溃口填补效果一样，即溃口面积为最小，则选择耗材最小的方案。
溃口数组长度m和木
