AlgoMooc
← 返回题库

P3211. 最佳升级时间窗

中等通过率 34% · 提交 99 · 通过 34
滑动窗口模拟不定滑窗

小慕负责维护一套在线系统,计划在某个连续时间段内进行升级。为了尽量减少升级对用户的影响,他需要根据系统过去一周内每小时的用户访问量,来预测最适合的升级窗口。 系统记录了过去168小时(7×24小时)的访问数据,以整数数组形式给出,表示从周一00:00到周日24:00的每小时访问量。小慕需要根据以下规则选择最佳升级: 1. 该时间窗内的累计用户访问量必须小于等于给定的。 2. 时间窗必须是连续的x个小时,x越大越好,且x不能超过168。 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

时间限制 1000 ms · 内存限制 128 MB

看不懂题目?点开图解(训练营专属)

登录后查看题目图解

题目图解为训练营学员专属内容,请先登录。

微信扫码登录还不是训练营学员?了解训练营 →
写完代码点「提交」,将对全部测试用例判题。