华为OD机试 - 水库溃坝填补 - 动态规划（Python/JS/C/C++ 新系统 200分）

华为OD机试 新系统 统一考试题库清单持续收录中以及考点说明Python/JS/C/C。专栏导读本专栏收录于《华为OD机试真题Python/JS/C/C》。刷的越多抽中的概率越大私信哪吒备注华为OD加入华为OD刷题交流群每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景发现新题目随时更新。一、题目描述一座水库在连续多日雨水的冲击下发生了溃坝事故解放军赶到现场救灾。其中水坝两侧坝岩是坚固且高度相等坝口用宽度为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 最小六、Python算法源码importsys# 比较两个状态谁更优# 状态格式(cover, wood_sum)# 1. cover 更大更优# 2. cover 相同则 wood_sum 更小更优defbetter(a,b):ifaisNone:returnbifbisNone:returnaifa[0]!b[0]:returnaifa[0]b[0]elsebreturnaifa[1]b[1]elsebdefsolve(data:str)-str:lines[line.strip()forlineindata.strip().splitlines()ifline.strip()]# 读取输入mint(lines[0])damlist(map(int,lines[1].split(,)))nint(lines[2])woodslist(map(int,lines[3].split(,)))# 两端坝岩高度kdam[0]# 计算所有需要填补的缺口深度depths[]foriinrange(1,m-1):depthk-dam[i]ifdepth0:depths.append(depth)# 没有缺口需要填补ifnotdepths:return0# 排序depths.sort()woods.sort()dlenlen(depths)# dp[i][j]# 前 i 个缺口、前 j 根木材时的最优状态dp[[(0,0)for_inrange(n1)]for_inrange(dlen1)]# 动态规划foriinrange(1,dlen1):depthdepths[i-1]forjinrange(1,n1):# 方案1不用第 j 根木材bestdp[i][j-1]# 方案2第 i 个缺口不填bestbetter(best,dp[i-1][j])# 方案3第 i 个缺口使用第 j 根木材prevdp[i-1][j-1]gainmin(depth,woods[j-1])use(prev[0]gain,prev[1]woods[j-1])bestbetter(best,use)dp[i][j]bestreturnstr(dp[dlen][n][1])if__name____main__:print(solve(sys.stdin.read()))七、JavaScript算法源码constfsrequire(fs);// 读取标准输入constinputfs.readFileSync(0,utf8).trim().split(/\n/).map(ss.trim());constmNumber(input[0]);constdaminput[1].split(,).map(sNumber(s.trim()));constnNumber(input[2]);constwoodsinput[3].split(,).map(sNumber(s.trim()));// 比较两个状态谁更优// 优先 cover 更大如果 cover 相同则 woodSum 更小functionbetter(a,b){if(a.cover!b.cover){returna.coverb.cover?a:b;}returna.woodSumb.woodSum?a:b;}constkdam[0];// 计算缺口深度constdepths[];for(leti1;im-1;i){constdepthk-dam[i];if(depth0){depths.push(depth);}}// 如果没有缺口输出 0if(depths.length0){console.log(0);process.exit(0);}// 排序depths.sort((a,b)a-b);woods.sort((a,b)a-b);// dp[i][j]前 i 个缺口、前 j 根木材时的最优状态constdpArray.from({length:depths.length1},()Array.from({length:n1},()({cover:0,woodSum:0})));// 动态规划for(leti1;idepths.length;i){constdepthdepths[i-1];for(letj1;jn;j){// 方案1不用第 j 根木材letbestdp[i][j-1];// 方案2第 i 个缺口不填bestbetter(best,dp[i-1][j]);// 方案3第 i 个缺口使用第 j 根木材constprevdp[i-1][j-1];constuse{cover:prev.coverMath.min(depth,woods[j-1]),woodSum:prev.woodSumwoods[j-1]};bestbetter(best,use);dp[i][j]best;}}// 输出最优方案的木材总高度console.log(dp[depths.length][n].woodSum);八、C算法源码#includestdio.h#includestdlib.h#includestring.h// 状态结构体// cover已减少的总面积// woodSum已使用木材总高度typedefstruct{intcover;intwoodSum;}State;// 比较两个状态返回更优状态Statebetter(State a,State b){if(a.cover!b.cover){returna.coverb.cover?a:b;}returna.woodSumb.woodSum?a:b;}// qsort 用的比较函数升序intcmpInt(constvoid*a,constvoid*b){return(*(int*)a)-(*(int*)b);}intmain(){intm,n;charline[1024];intdam[105];intwoods[105];intdepths[105];// 读取坝口数组长度scanf(%d,m);// 读取坝口数组字符串scanf(%s,line);// 解析坝口数组intidx0;char*tokenstrtok(line,,);while(token!NULL){dam[idx]atoi(token);tokenstrtok(NULL,,);}// 读取木材数组长度scanf(%d,n);// 读取木材数组字符串scanf(%s,line);// 解析木材数组idx0;tokenstrtok(line,,);while(token!NULL){woods[idx]atoi(token);tokenstrtok(NULL,,);}// 两端坝岩高度intkdam[0];// 计算所有缺口深度intdLen0;for(inti1;im-1;i){intdepthk-dam[i];if(depth0){depths[dLen]depth;}}// 没有需要填补的缺口if(dLen0){printf(0\n);return0;}// 排序qsort(depths,dLen,sizeof(int),cmpInt);qsort(woods,n,sizeof(int),cmpInt);// dp[i][j]前 i 个缺口、前 j 根木材时的最优状态State dp[105][105];// 初始化for(inti0;idLen;i){for(intj0;jn;j){dp[i][j].cover0;dp[i][j].woodSum0;}}// 动态规划for(inti1;idLen;i){intdepthdepths[i-1];for(intj1;jn;j){// 方案1不用第 j 根木材State bestdp[i][j-1];// 方案2第 i 个缺口不填bestbetter(best,dp[i-1][j]);// 方案3第 i 个缺口使用第 j 根木材State prevdp[i-1][j-1];State use;use.coverprev.cover(depthwoods[j-1]?depth:woods[j-1]);use.woodSumprev.woodSumwoods[j-1];bestbetter(best,use);dp[i][j]best;}}// 输出最优方案耗材printf(%d\n,dp[dLen][n].woodSum);return0;}九、C算法源码#includebits/stdc.husingnamespacestd;// 状态结构体// cover已减少的总面积// woodSum已消耗的木材总高度structState{intcover;intwoodSum;};// 比较两个状态返回更优状态// 1. cover 更大更优// 2. cover 相同woodSum 更小更优StatebetterState(constStatea,constStateb){if(a.cover!b.cover){returna.coverb.cover?a:b;}returna.woodSumb.woodSum?a:b;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intm,n;cinm;string s;cins;// 解析坝口数组vectorintdam;string token;stringstreamss1(s);while(getline(ss1,token,,)){dam.push_back(stoi(token));}cinn;cins;// 解析木材数组vectorintwoods;stringstreamss2(s);while(getline(ss2,token,,)){woods.push_back(stoi(token));}// 两端坝岩高度intkdam[0];// 计算缺口深度vectorintdepths;for(inti1;im-1;i){intdepthk-dam[i];if(depth0){depths.push_back(depth);}}// 没有缺口需要填补if(depths.empty()){cout0\n;return0;}// 排序sort(depths.begin(),depths.end());sort(woods.begin(),woods.end());// dp[i][j]前 i 个缺口、前 j 根木材时的最优状态vectorvectorStatedp(depths.size()1,vectorState(woods.size()1,{0,0}));// 动态规划for(inti1;i(int)depths.size();i){intdepthdepths[i-1];for(intj1;j(int)woods.size();j){// 方案1不用第 j 根木材State bestdp[i][j-1];// 方案2第 i 个缺口不填bestbetterState(best,dp[i-1][j]);// 方案3第 i 个缺口使用第 j 根木材State prevdp[i-1][j-1];State use{prev.covermin(depth,woods[j-1]),prev.woodSumwoods[j-1]};bestbetterState(best,use);dp[i][j]best;}}// 输出答案coutdp[depths.size()][woods.size()].woodSum\n;return0;}下一篇华为OD机试真题 - 简易内存池Python/JS/C/C 新系统 200分本文收录于华为OD机试真题Python/JS/C/C刷的越多抽中的概率越大私信哪吒备注华为OD加入华为OD刷题交流群每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景发现新题目随时更新。