小慕负责维护一套在线系统,计划在某个连续时间段内进行升级。为了尽量减少升级对用户的影响,他需要根据系统过去一周内每小时的用户访问量,来预测最适合的升级窗口。 系统记录了过去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