拓冰网站定制 
查找最佳充电策略(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⩽24，1 ⩽ h o u r s ⩽ p r i c e R e c o r d s 1 \leqslant hours \leqslant priceRecords1⩽hours⩽priceRecords，1 ⩽ 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 25+15+20=6025+15+20=60
- 1 11为起始索引时 总费用15 + 20 + 18 = 53 15+20+18=5315+20+18=53
- 2 22为起始索引时 总费用20 + 18 + 12 = 50 20+18+12=5020+18+12=50
- 3 33为起始索引时 总费用18 + 12 + 25 = 55 18+12+25=5518+12+25=55
- 4 44为起始索引时 总费用12 + 25 + 30 = 67 12+25+30=6712+25+30=67
- 5 55为起始索引时 总费用25 + 30 + 28 = 83 25+30+28=8325+30+28=83
- 6 66为起始索引时 总费用30 + 28 + 22 = 80 30+28+22=8030+28+22=80
- 7 77为起始索引时 总费用28 + 22 + 16 = 66 28+22+16=6628+22+16=66
- 8 88为起始索引时 总费用22 + 16 + 14 = 52 22+16+14=5222+16+14=52
- 9 99为起始索引时 总费用16 + 14 + 35 = 65 16+14+35=6516+14+35=65
连续3 33小时的最低电价时段是索引2 - 4 2\text{-}42-4，价格分别为20 , 18 , 12 20, 18, 1220,18,12，总费用= 20 + 18 + 12 = 50 =20+18+12=50=20+18+12=50分最低
因此充电最低时间起始索引为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 23+35+67+68=19323+35+67+68=193
- 1 11为起始索引时 总费用35 + 67 + 68 + 89 = 259 35+67+68+89=25935+67+68+89=259
- 2 22为起始索引时 总费用67 + 68 + 89 + 12 = 236 67+68+89+12=23667+68+89+12=236
- 3 33为起始索引时 总费用68 + 89 + 12 + 24 = 193 68+89+12+24=19368+89+12+24=193
- 4 44为起始索引时 总费用89 + 12 + 24 + 37 = 162 89+12+24+37=16289+12+24+37=162
- 5 55为起始索引时 总费用12 + 24 + 37 + 57 = 130 12+24+37+57=13012+24+37+57=130
- 6 66为起始索引时 总费用24 + 37 + 57 + 10 = 128 24+37+57+10=12824+37+57+10=128
- 7 77为起始索引时 总费用37 + 57 + 10 + 12 = 116 37+57+10+12=11637+57+10+12=116
- 8 88为起始索引时 总费用57 + 10 + 12 + 45 = 124 57+10+12+45=12457+10+12+45=124
连续4 44小时的最低电价时段是索引7 - 10 7\text{-}107-10，价格分别为37 , 57 , 10 , 12 37, 57, 10, 1237,57,10,12，总费用= 37 + 57 + 10 + 12 = 116 =37+57+10+12=116=37+57+10+12=116分最低
因此充电最低时间起始索引为7 77
题解
思路：滑动窗口
固定滑动窗口模板题，使用
sum记录窗口内价格总和，使用minSum记录出现的最小窗口总和，使用res记录最小窗口总和对应起始下标。窗口右边界不断右移，进行
sum += prices[right],根据情况进行如下处理- 没有达到要求
hours长度，不进行处理 - 首次形成
hours长度时，更新minSum = sum并且res = 0 - 后续窗口移动时，删除窗口左边离开的元素，并将
sum 和 minSum进行对比，尝试更新minSum 和 res。
- 没有达到要求
当
right >= n结束，返回res即可。
c++
#include<bits/stdc++.h>#include<vector>usingnamespacestd;intsolve(intpriceRecords,inthours,vector<int>&prices){intres=0;intminSum=INT_MAX;intsum=0;// 滑动窗口for(intright=0;right<priceRecords;right++){sum+=prices[right];if(right<hours-1){continue;}if(right==hours-1){res=0;minSum=sum;continue;}sum-=prices[right-hours];if(sum<minSum){minSum=sum;res=right-hours+1;}}returnres;}intmain(){intpriceRecords;inthours;cin>>priceRecords;cin>>hours;vector<int>price(priceRecords);for(inti=0;i<priceRecords;i++){cin>>price[i];}cout<<solve(priceRecords,hours,price);return0;}Java
importjava.util.*;publicclassMain{staticintsolve(intpriceRecords,inthours,int[]prices){intres=0;intminSum=Integer.MAX_VALUE;intsum=0;// 滑动窗口for(intright=0;right<priceRecords;right++){sum+=prices[right];if(right<hours-1){continue;}if(right==hours-1){res=0;minSum=sum;continue;}sum-=prices[right-hours];if(sum<minSum){minSum=sum;res=right-hours+1;}}returnres;}publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);intpriceRecords=sc.nextInt();inthours=sc.nextInt();int[]price=newint[priceRecords];for(inti=0;i<priceRecords;i++){price[i]=sc.nextInt();}System.out.print(solve(priceRecords,hours,price));sc.close();}}Python
importsysdefsolve(priceRecords,hours,prices):res=0minSum=float('inf')sum=0# 滑动窗口forrightinrange(priceRecords):sum+=prices[right]ifright<hours-1:continueifright==hours-1:res=0minSum=sumcontinuesum-=prices[right-hours]ifsum<minSum:minSum=sumres=right-hours+1returnres priceRecords=int(sys.stdin.readline())hours=int(sys.stdin.readline())prices=list(map(int,sys.stdin.readline().split()))print(solve(priceRecords,hours,prices))JavaScript
constreadline=require("readline");constrl=readline.createInterface({input:process.stdin,output:process.stdout});letinput=[];rl.on("line",line=>{input.push(line);});rl.on("close",()=>{letindex=0;letpriceRecords=Number(input[index++]);lethours=Number(input[index++]);letprices=input[index].split(" ").map(Number);console.log(solve(priceRecords,hours,prices));});functionsolve(priceRecords,hours,prices){letres=0;letminSum=Infinity;letsum=0;// 滑动窗口for(letright=0;right<priceRecords;right++){sum+=prices[right];if(right<hours-1){continue;}if(right===hours-1){res=0;minSum=sum;continue;}sum-=prices[right-hours];if(sum<minSum){minSum=sum;res=right-hours+1;}}returnres;}Go
packagemainimport("bufio""fmt""os")funcsolve(priceRecordsint,hoursint,prices[]int)int{res:=0minSum:=int(^uint(0)>>1)sum:=0// 滑动窗口forright:=0;right<priceRecords;right++{sum+=prices[right]ifright<hours-1{continue}ifright==hours-1{res=0minSum=sumcontinue}sum-=prices[right-hours]ifsum<minSum{minSum=sum res=right-hours+1}}returnres}funcmain(){in:=bufio.NewReader(os.Stdin)varpriceRecords,hoursintfmt.Fscan(in,&priceRecords)fmt.Fscan(in,&hours)price:=make([]int,priceRecords)fori:=0;i<priceRecords;i++{fmt.Fscan(in,&price[i])}fmt.Println(solve(priceRecords,hours,price))}C语言
#include<stdio.h>#include<limits.h>intsolve(intpriceRecords,inthours,intprices[]){intres=0;intminSum=INT_MAX;intsum=0;// 滑动窗口for(intright=0;right<priceRecords;right++){sum+=prices[right];if(right<hours-1){continue;}if(right==hours-1){res=0;minSum=sum;continue;}sum-=prices[right-hours];if(sum<minSum){minSum=sum;res=right-hours+1;}}returnres;}intmain(){intpriceRecords;inthours;scanf("%d",&priceRecords);scanf("%d",&hours);intprice[priceRecords];for(inti=0;i<priceRecords;i++){scanf("%d",&price[i]);}printf("%d",solve(priceRecords,hours,price));return0;}