华为OD机试 - 水库溃坝填补 - 动态规划（Java 新系统 200分）

华为OD机试 新系统 题库疯狂收录中刷题点这里专栏导读本专栏收录于《华为OD机试JAVA真题》。刷的越多抽中的概率越大私信哪吒备注华为OD加入华为OD刷题交流群每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景发现新题目随时更新全天CSDN在线答疑。一、题目描述一座水库在连续多日雨水的冲击下发生了溃坝事故解放军赶到现场救灾。其中水坝两侧坝岩是坚固且高度相等坝口用宽度为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和木材数组长度n均为 0 且100,坝岩高度k和木材高度均为 0 且15坝口数组规定第1个高度和最后一个高度是坝岩的高度-锚定高度两者高度相等绝对不会溃坝无需填补坝口可能会存在多个二、输入描述输入第一行为坝口数组长度第二行为坝口数组第三行为木材数组长度第四行为木材数组三、输出描述填补坝口耗费的木材的总高度四、测试用例测试用例11、输入38,0,827,62、输出73、说明只有一个缺口深度为 8-08。木材有 7 和 6都不能填满但 7 效果更好。最优使用木材 7输出 7。测试用例21、输入510,3,0,2,1064,8,6,4,5,62、输出203、说明缺口深度分别为10-3710-01010-28最优搭配可以做到减少面积最大同时总木材最小结果为 20。五、解题思路1、问题分析设两侧坝岩高度都是 k则中间每个位置如果当前高度是 h它还差depth k - h这就是该位置的“缺口深度”。如果给这个位置放一根高度为 w 的木材那么这个位置能减少的坝口面积是min(depth, w)因为木材只能整根使用不能截断即使木材超过缺口深度超过部分也不会继续减少面积每个位置最多放 1 根木材每根木材最多用 1 次于是问题变成从若干缺口深度和若干木材中进行一一匹配使得总减少面积最大如果总减少面积相同则木材总高度最小最终输出所使用木材总高度2、为什么用动态规划因为这是一个“有序匹配最优化”问题。把缺口深度数组排序木材数组排序然后做二维动态规划dp[i][j] 表示前 i 个缺口、前 j 根木材时的最优结果每一步有 3 种决策不用第 j 根木材不填第 i 个缺口第 i 个缺口使用第 j 根木材状态里需要同时保存两个值cover已经减少的总面积woodSum使用木材总高度比较优先级先让 cover 最大若 cover 相同再让 woodSum 最小六、Java算法源码publicclassOdTest{// 状态类// cover当前方案总共减少了多少坝口面积// woodSum当前方案总共消耗了多少木材高度staticclassState{intcover;intwoodSum;State(intcover,intwoodSum){this.covercover;this.woodSumwoodSum;}}// 比较两个状态谁更优// 规则// 1. 优先选择减少面积更多的方案cover 更大// 2. 如果减少面积相同则选择耗材更少的方案woodSum 更小staticStatebetter(Statea,Stateb){if(anull)returnb;if(bnull)returna;if(a.cover!b.cover){returna.coverb.cover?a:b;}returna.woodSumb.woodSum?a:b;}publicstaticvoidmain(String[]args){ScannerscnewScanner(System.in);// 读取坝口数组长度intmInteger.parseInt(sc.nextLine().trim());// 读取坝口数组String[]damStrsc.nextLine().trim().split(,);int[]damnewint[m];for(inti0;im;i){dam[i]Integer.parseInt(damStr[i].trim());}// 读取木材数组长度intnInteger.parseInt(sc.nextLine().trim());// 读取木材数组String[]woodStrsc.nextLine().trim().split(,);int[]woodsnewint[n];for(inti0;in;i){woods[i]Integer.parseInt(woodStr[i].trim());}// 两端坝岩高度相等题意保证成立取 dam[0] 即可intkdam[0];// 把中间位置转成“缺口深度”// 只有 depth 0 的位置才需要填补ListIntegerdepthListnewArrayList();for(inti1;im-1;i){intdepthk-dam[i];if(depth0){depthList.add(depth);}}// 如果没有需要填补的缺口直接输出 0if(depthList.isEmpty()){System.out.println(0);return;}// 排序// 缺口深度升序木材高度升序Collections.sort(depthList);Arrays.sort(woods);intdLendepthList.size();// dp[i][j]// 表示前 i 个缺口、前 j 根木材时的最优状态State[][]dpnewState[dLen1][n1];// 初始化// 前 0 个缺口不管有多少木材答案都是 cover0, woodSum0for(intj0;jn;j){dp[0][j]newState(0,0);}// 没有木材时也只能做到减少面积为 0耗材为 0for(inti1;idLen;i){dp[i][0]newState(0,0);}// 动态规划for(inti1;idLen;i){intdepthdepthList.get(i-1);for(intj1;jn;j){// 方案1不用第 j 根木材Statebestdp[i][j-1];// 方案2第 i 个缺口不填bestbetter(best,dp[i-1][j]);// 方案3第 i 个缺口使用第 j 根木材Stateprevdp[i-1][j-1];intgainMath.min(depth,woods[j-1]);// 本次能减少的面积StateusenewState(prev.covergain,prev.woodSumwoods[j-1]);bestbetter(best,use);dp[i][j]best;}}// 最终输出最优方案消耗的木材总高度System.out.println(dp[dLen][n].woodSum);}}七、效果展示1、输入57,3,0,0,764,7,4,3,3,52、输出163、说明缺口深度为 [4,7,7]。最优选择木材 [4,7,5]4 填深度 47 填深度 75 填深度 7总耗材为 47516这是题干中的典型例子。下一篇华为OD机试 - 简易内存池 - 逻辑分析Java 新系统 200分本专栏收录于《华为OD机试JAVA真题》。刷的越多抽中的概率越大私信哪吒备注华为OD加入华为OD刷题交流群每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景发现新题目随时更新全天CSDN在线答疑。