华为OD机考双机位C卷 - 最佳升级时间窗 (C++ Python JAVA JS GO)

最佳升级时间窗

2025华为OD机试双机位C卷 - 华为OD上机考试双机位C卷 100分题型

华为OD机试双机位C卷真题目录点击查看: 华为OD机试双机位C卷真题题库目录｜机考题库 + 算法考点详解

题目描述

有一套系统需升级，为减小系统升级期间的影响，需根据系统过去一段时间内的每小时平均访问数据，来预测最佳升级时间窗。

现给长度为168（7*24）的整数数组，表示一个周期（假设从周一00:00到周日24:00）的每小时历史数据，最佳升级时间窗选择规则如下：

1：时间窗内累计用户访问量必须小于等于给定的容忍值。

2：时间窗必须是连续的x个小时，最大的x即为最佳升级时间窗，且不超过7*24.

3：时间窗允许跨周期，例如当前周期的第167小时到下一周期的第166小时，是一个长度为168的时间窗。

请计算最佳升级时间窗，并返回其开始时间和结束时间的数组下标。如果存在多个最佳升级时间窗，返回开始时间下标最小的一个。

输入描述

第一行为整数n，表示给定的升级影响的容忍值，取值范围：[0, 2^31]。

第二行为7 * 24个整数，表示一个周期（7*24）的每个小时用户访问量，每个值的范围：[0, 2^31]。

输出描述

两个整数，分别表示所计算出的最佳升级时间窗的开始时间下标（包含）和结束时间下标（包含），不存在时返回 -1 -1 。

用例1

输入

6 1 2 3 4 5 6 7 8 9 10 11 12 12 11 10 9 8 7 6 5 4 3 2 1 1 2 3 4 5 6 7 8 9 10 11 12 12 11 10 9 8 7 6 5 4 3 2 1 1 2 3 4 5 6 7 8 9 10 11 12 12 11 10 9 8 7 6 5 4 3 2 1 1 2 3 4 5 6 7 8 9 10 11 12 12 11 10 9 8 7 6 5 4 3 2 1 1 2 3 4 5 6 7 8 9 10 11 12 12 11 10 9 8 7 6 5 4 3 2 1 1 2 3 4 5 6 7 8 9 10 11 12 12 11 10 9 8 7 6 5 4 3 2 1 1 2 3 4 5 6 7 8 9 10 11 12 12 11 10 9 8 7 6 5 4 3 2 1

输出

22 25

说明

最佳升级窗口为：2 1 1 2

题解

思路：滑动窗口

1. 这类题就是典型使用滑动窗口解决的题
2. 然后思考怎么解决题目提到的时间窗允许跨周期的问题，对于这类首尾可以连接的问题，可以将数组进行扩容168*2将数组重复一次，跨周期的窗口就可以变为普通连续子数组问题。
3. 接下来就是正常滑动窗口处理逻辑,定义左边界left = 0, right =0, 窗口和windowsSum =0，maxLen= 0, resLeft = -1, resRight = -1, 接下来就是循环移动右边界，每次执行以下操作
   • windowsSum += seq[i]
   • 如果windowsSum > n,不断收缩左边界直到windowSum <=n结束，收缩边界每次执行windowsSum -= seq[left], left++
   • 经过上面就会得到一个合法的窗口，计算长度为len = right - left + 1, 然后根据与maxLen更新结果即可。这里有个易错点：之前将原数组扩容了，可能存在n > sum(originalSeq)这样长度可以超过168所以当len == 168可以直接退出滑动窗口逻辑。
   • 优化点:如果当left >= 168也可以提前退出滑动窗口逻辑，因为这里又进入了第一个周期一样的逻辑，没必要重复找。当前不做这个优化这道题也不会超时。
4. 执行3的逻辑之后，此时根据maxLen的值输出结果
   • maxLen = 0: 说明不存在这样窗口直接输出-1 -1
   • maxLen !=0: 说明存在窗口，此时需要输出(resLeft % 168) (resRight % 168),%128主要是处于跨周期的情况要保证输出的为[0,167]范围。

c++

#include<iostream> #include<vector> #include<string> #include <utility> #include <sstream> #include<algorithm> #include<cmath> #include<map> using namespace std; int main() { long n; cin >> n; // 由于可以首尾相连，直接将数组重复一次，这样跨周期的窗口就可以变为普通连续子数组问题 vector<long> seq(168 * 2); for (int i = 0; i < 168; i++) { cin >> seq[i]; seq[i + 168] = seq[i]; } int maxLen = 0; int resLeft = -1, resRight = -1; long windowSum = 0; int left = 0; for (int right = 0; right < 168 * 2; right++) { windowSum += seq[right]; // 保证窗口和不超过容忍值 while (windowSum > n) { windowSum -= seq[left]; left++; } // 和第一个周期重复了 if (left >= 168) { break; } int len = right - left + 1; if (len > maxLen) { maxLen = len; resLeft = left; resRight = right; } // 已经达到最大周期，可以直接退出 if (len == 168) { break; } } if (maxLen == 0) { cout << "-1 -1"; }else { cout << resLeft % 168 << " " << resRight % 168; } return 0; }

JAVA

import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); long n = sc.nextLong(); // 由于可以首尾相连，直接将数组重复一次，这样跨周期的窗口就可以变为普通连续子数组问题 long[] seq = new long[168 * 2]; for (int i = 0; i < 168; i++) { seq[i] = sc.nextLong(); seq[i + 168] = seq[i]; } int maxLen = 0; int resLeft = -1, resRight = -1; long windowSum = 0; int left = 0; for (int right = 0; right < 168 * 2; right++) { windowSum += seq[right]; // 保证窗口和不超过容忍值 while (windowSum > n) { windowSum -= seq[left]; left++; } // 和第一个周期重复了 if (left >= 168) { break; } int len = right - left + 1; if (len > maxLen) { maxLen = len; resLeft = left; resRight = right; } // 已经达到最大周期，可以直接退出 if (len == 168) { break; } } if (maxLen == 0) { System.out.println("-1 -1"); } else { System.out.println(resLeft % 168 + " " + resRight % 168); } } }

Python

n=int(input())arr=list(map(int,input().split()))# 由于可以首尾相连，重复一次seq=arr+arr maxLen=0resLeft=-1resRight=-1windowSum=0left=0forrightinrange(len(seq)):windowSum+=seq[right]# 保证窗口和不超过容忍值whilewindowSum>n:windowSum-=seq[left]left+=1# 和第一个周期重复了ifleft>=168:breaklength=right-left+1iflength>maxLen:maxLen=length resLeft=left resRight=right# 已经达到最大周期，可以直接退出iflength==168:breakifmaxLen==0:print("-1 -1")else:print(resLeft%168,resRight%168)

JavaScript

letinput=[];require('readline').createInterface({input:process.stdin,output:process.stdout}).on('line',line=>input.push(line)).on('close',()=>{letn=parseInt(input[0]);letarr=input[1].split(' ').map(Number);// 由于可以首尾相连，重复一次letseq=arr.concat(arr);letmaxLen=0;letresLeft=-1,resRight=-1;letwindowSum=0;letleft=0;for(letright=0;right<seq.length;right++){windowSum+=seq[right];// 保证窗口和不超过容忍值while(windowSum>n){windowSum-=seq[left];left++;}// 和第一个周期重复了if(left>=168)break;letlen=right-left+1;if(len>maxLen){maxLen=len;resLeft=left;resRight=right;}// 已经达到最大周期，可以直接退出if(len==168)break;}if(maxLen==0){console.log("-1 -1");}else{console.log(resLeft%168,resRight%168);}});

Go

packagemainimport("fmt")funcmain(){varnint64fmt.Scan(&n)seq:=make([]int64,168*2)fori:=0;i<168;i++{fmt.Scan(&seq[i])seq[i+168]=seq[i]// 重复一次}maxLen:=0resLeft,resRight:=-1,-1varwindowSumint64=0left:=0forright:=0;right<168*2;right++{windowSum+=seq[right]// 保证窗口和不超过容忍值forwindowSum>n{windowSum-=seq[left]left++}// 和第一个周期重复了ifleft>=168{break}length:=right-left+1iflength>maxLen{maxLen=length resLeft=left resRight=right}// 已经达到最大周期，可以直接退出iflength==168{break}}ifmaxLen==0{fmt.Println("-1 -1")}else{fmt.Println(resLeft%168,resRight%168)}}