解题思路
本题是固定长度滑动窗口 + 无效点过滤,可用双指针/滑动窗口在 O(n) 时间内求最小合法窗口和。
- 合法性:长度为 w 的窗口内任意
scores[i]==0 则该窗口非法,必须跳过。
- 滑动维护:对起点
start 从 0 到 n−w,维护窗口和 window_sum 与窗口内 0 的个数 zero_count;右移一步时减去离开元素、加入进入元素并同步更新 zero_count。
- 最优与平局:仅当
zero_count==0 时参与比较;若 window_sum 严格小于当前最小和则更新答案。按 start 递增扫描,相等和时不更新,自然得到最早起始下标。
- 无解:扫描结束仍无合法窗口,返回
[-1, 0]。
P14401.数据中心最佳维护窗口(100分)
题目内容
某数据中心记录了连续 N 小时内每小时的服务器负载得分,记录在数组 scores 中;0 表示该小时无效(服务器故障)。
需要选择连续 W 小时的窗口作为最佳的维护窗口,满足如下规则:
- 窗口内不能包含无效小时
- 窗口满足负载得分总和最小;若存在多个,选取起始小时最早的
- 不存在满足条件的窗口时,输出 [−1,0]
输入描述
N:总小时数 (1≤N≤100000)
W:窗口长度 (1≤W≤min(N,10000))
scores:长度为 N 的数组,第 i 个值表示第 i 小时负载得分 (0≤scores[i]≤1000)
输出描述
包含 2 个整数的数组 — [起始小时编号, 最小负载总和] 或 [−1,0]
样例1
输入
9,2,[10,5,20,10,5,15,10,5,25]
输出
[0,15]
说明
3 个窗口([0,1],[3,4],[6,7])总得分都是 15,所以选最早的从 0 开始,得分是 15
样例2
输入
5,3,[0,5,0,8,12]
输出
[-1,0]
说明
找不到连续 3 个小时的维护窗口,所以输出 [−1,0]
样例3
输入
12,4,[10,2,1,0,15,0,8,3,6,12,6,9]
输出
[7,27]
说明
前 6 个数都没有连续 4 个小时的维护窗口,从下标为 6 开始有连续 4 小时的维护窗口,需要依次计算负载得分,从下标 6 开始的 4 个小时维护窗口总得分是 29,从下标 7 开始是 27,从下标 8 开始是 33,所以从下标 7 开始负载总得分最小是 27,因此输出 [7,27]