华为OD机试新系统真题 【查找最佳充电策略】

查找最佳充电策略(C/C/Js/Java/Py/Go)题解华为OD机试新系统真题 华为OD上机考试新系统真题 8月9号 100分题型华为OD机试新系统真题目录点击查看: 华为OD机试新系统真题题库目录机考题库 算法考点详解题目内容给定一个一维数组p r i c e A r r a y priceArraypriceArray表示未来p r i c e R e c o r d s priceRecordspriceRecords小时内每小时的电价单位分/kWh。找出充电成本最低的连续h o u r s hourshours个小时时间段的开始时刻点。若存在多种成本最低方案优先返回最低成本方案的最早的时刻点。输入描述参数1 11整数p r i c e R e c o r d s priceRecordspriceRecords表示电价记录数量参数2 22整数h o u r s hourshours表示连续小时数参数3 33一维数组p r i c e A r r a y priceArraypriceArray表示每小时的电价p r i c e 1 ∼ p r i c e N price1 \sim priceNprice1∼priceN以空格分隔约束条件1 ⩽ p r i c e R e c o r d s ⩽ 24 1 \leqslant priceRecords \leqslant 241⩽priceRecords⩽241 ⩽ h o u r s ⩽ p r i c e R e c o r d s 1 \leqslant hours \leqslant priceRecords1⩽hours⩽priceRecords1 ⩽ p r i c e 1 ∼ p r i c e N ⩽ 100 1 \leqslant price1 \sim priceN \leqslant 1001⩽price1∼priceN⩽100输出描述返回一个整数表示最优充电时段的起始索引从0 00开始。样例1输入12 3 25 15 20 18 12 25 30 28 22 16 14 35输出2说明连续时间段为3 33从0 00时刻开始分段计算最小总成本0 00为起始索引时 总费用25 15 20 60 25152060251520601 11为起始索引时 总费用15 20 18 53 15201853152018532 22为起始索引时 总费用20 18 12 50 20181250201812503 33为起始索引时 总费用18 12 25 55 18122555181225554 44为起始索引时 总费用12 25 30 67 12253067122530675 55为起始索引时 总费用25 30 28 83 25302883253028836 66为起始索引时 总费用30 28 22 80 30282280302822807 77为起始索引时 总费用28 22 16 66 28221666282216668 88为起始索引时 总费用22 16 14 52 22161452221614529 99为起始索引时 总费用16 14 35 65 1614356516143565连续3 33小时的最低电价时段是索引2 - 4 2\text{-}42-4价格分别为20 , 18 , 12 20, 18, 1220,18,12总费用 20 18 12 50 2018125020181250分最低因此充电最低时间起始索引为2 22样例2输入12 4 23 35 67 68 89 12 24 37 57 10 12 45输出7说明连续时间段为4 44从0 00时刻开始分段计算最小总成本0 00为起始索引时 总费用23 35 67 68 193 23356768193233567681931 11为起始索引时 总费用35 67 68 89 259 35676889259356768892592 22为起始索引时 总费用67 68 89 12 236 67688912236676889122363 33为起始索引时 总费用68 89 12 24 193 68891224193688912241934 44为起始索引时 总费用89 12 24 37 162 89122437162891224371625 55为起始索引时 总费用12 24 37 57 130 12243757130122437571306 66为起始索引时 总费用24 37 57 10 128 24375710128243757101287 77为起始索引时 总费用37 57 10 12 116 37571012116375710121168 88为起始索引时 总费用57 10 12 45 124 5710124512457101245124连续4 44小时的最低电价时段是索引7 - 10 7\text{-}107-10价格分别为37 , 57 , 10 , 12 37, 57, 10, 1237,57,10,12总费用 37 57 10 12 116 3757101211637571012116分最低因此充电最低时间起始索引为7 77题解思路滑动窗口固定滑动窗口模板题使用sum记录窗口内价格总和使用minSum记录出现的最小窗口总和使用res记录最小窗口总和对应起始下标。窗口右边界不断右移进行sum prices[right],根据情况进行如下处理没有达到要求hours长度不进行处理首次形成hours长度时更新minSum sum并且res 0后续窗口移动时删除窗口左边离开的元素并将sum 和 minSum进行对比尝试更新minSum 和 res。当right n结束返回res即可。c#includebits/stdc.h#includevectorusingnamespacestd;intsolve(intpriceRecords,inthours,vectorintprices){intres0;intminSumINT_MAX;intsum0;// 滑动窗口for(intright0;rightpriceRecords;right){sumprices[right];if(righthours-1){continue;}if(righthours-1){res0;minSumsum;continue;}sum-prices[right-hours];if(summinSum){minSumsum;resright-hours1;}}returnres;}intmain(){intpriceRecords;inthours;cinpriceRecords;cinhours;vectorintprice(priceRecords);for(inti0;ipriceRecords;i){cinprice[i];}coutsolve(priceRecords,hours,price);return0;}Javaimportjava.util.*;publicclassMain{staticintsolve(intpriceRecords,inthours,int[]prices){intres0;intminSumInteger.MAX_VALUE;intsum0;// 滑动窗口for(intright0;rightpriceRecords;right){sumprices[right];if(righthours-1){continue;}if(righthours-1){res0;minSumsum;continue;}sum-prices[right-hours];if(summinSum){minSumsum;resright-hours1;}}returnres;}publicstaticvoidmain(String[]args){ScannerscnewScanner(System.in);intpriceRecordssc.nextInt();inthourssc.nextInt();int[]pricenewint[priceRecords];for(inti0;ipriceRecords;i){price[i]sc.nextInt();}System.out.print(solve(priceRecords,hours,price));sc.close();}}Pythonimportsysdefsolve(priceRecords,hours,prices):res0minSumfloat(inf)sum0# 滑动窗口forrightinrange(priceRecords):sumprices[right]ifrighthours-1:continueifrighthours-1:res0minSumsumcontinuesum-prices[right-hours]ifsumminSum:minSumsumresright-hours1returnres priceRecordsint(sys.stdin.readline())hoursint(sys.stdin.readline())priceslist(map(int,sys.stdin.readline().split()))print(solve(priceRecords,hours,prices))JavaScriptconstreadlinerequire(readline);constrlreadline.createInterface({input:process.stdin,output:process.stdout});letinput[];rl.on(line,line{input.push(line);});rl.on(close,(){letindex0;letpriceRecordsNumber(input[index]);lethoursNumber(input[index]);letpricesinput[index].split( ).map(Number);console.log(solve(priceRecords,hours,prices));});functionsolve(priceRecords,hours,prices){letres0;letminSumInfinity;letsum0;// 滑动窗口for(letright0;rightpriceRecords;right){sumprices[right];if(righthours-1){continue;}if(righthours-1){res0;minSumsum;continue;}sum-prices[right-hours];if(summinSum){minSumsum;resright-hours1;}}returnres;}Gopackagemainimport(bufiofmtos)funcsolve(priceRecordsint,hoursint,prices[]int)int{res:0minSum:int(^uint(0)1)sum:0// 滑动窗口forright:0;rightpriceRecords;right{sumprices[right]ifrighthours-1{continue}ifrighthours-1{res0minSumsumcontinue}sum-prices[right-hours]ifsumminSum{minSumsum resright-hours1}}returnres}funcmain(){in:bufio.NewReader(os.Stdin)varpriceRecords,hoursintfmt.Fscan(in,priceRecords)fmt.Fscan(in,hours)price:make([]int,priceRecords)fori:0;ipriceRecords;i{fmt.Fscan(in,price[i])}fmt.Println(solve(priceRecords,hours,price))}C语言#includestdio.h#includelimits.hintsolve(intpriceRecords,inthours,intprices[]){intres0;intminSumINT_MAX;intsum0;// 滑动窗口for(intright0;rightpriceRecords;right){sumprices[right];if(righthours-1){continue;}if(righthours-1){res0;minSumsum;continue;}sum-prices[right-hours];if(summinSum){minSumsum;resright-hours1;}}returnres;}intmain(){intpriceRecords;inthours;scanf(%d,priceRecords);scanf(%d,hours);intprice[priceRecords];for(inti0;ipriceRecords;i){scanf(%d,price[i]);}printf(%d,solve(priceRecords,hours,price));return0;}