数据中心最佳维护窗口

2026 华为OD机试真题 6月17日华为OD上机新系统考试真题 100 分题型

点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解

题目描述

某数据中心记录了连续 N 小时内每小时的服务器负载得分，记录在数组 scores 中；0 表示该小时无效（服务器故障）。 需要选择连续 W 小时的窗口作为最佳的维护窗口，满足如下规则：

1. 窗口内不能包含无效小时
2. 窗口满足负载得分总和最小；若存在多个，选取起始小时最早的
3. 不存在满足条件的窗口时，输出 [−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

输出

8,17

说明

有效窗口：[8,9,10,11]=[3,6,12,6]，得分17

解题思路

本题是一个 滑动窗口 问题，需要在长度为 N 的数组中找到长度为 W 的连续子数组，要求该子数组：

1. 不包含任何 0 元素（所有小时都有效）
2. 在所有满足条件的窗口中，选择总得分最小的
3. 若有多个最小值，选择起始位置最早的

关键点：

• 使用滑动窗口维护当前窗口内的元素和与0的个数
• 当窗口内0的个数为0时，该窗口是有效的
• 在有效窗口中选择sum最小的

算法步骤：

1. 初始化第一个窗口，计算窗口和与0的个数
2. 如果首个窗口有效且sum更小，更新最优结果
3. 滑动窗口：移出左边元素，加入右边元素
4. 重复检查并更新最优结果

复杂度：

• 时间：O(N)，每个元素最多遍历两次
• 空间：O(1)

Java

import java.util.*;
import java.util.stream.*;

/**
 * 华为OD机试真题 - 数据中心最佳维护窗口
 */
public class Main {
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取 N 和 W
        int n = Integer.parseInt(scanner.nextLine().trim());
        int w = Integer.parseInt(scanner.nextLine().trim());
        
        // 读取 scores 数组（逗号分隔）
        String[] scoreStrs = scanner.nextLine().trim().split(",");
        int[] scores = new int[n];
        for (int i = 0; i < n; i++) {
            scores[i] = Integer.parseInt(scoreStrs[i].trim());
        }
        
        // 调用算法
        int[] result = findMaintenanceWindow(n, w, scores);
        
        // 输出结果（逗号分隔）
        System.out.println(result[0] + "," + result[1]);
    }
    
    /**
     * 核心算法：查找最佳维护窗口
     */
    public static int[] findMaintenanceWindow(int n, int w, int[] scores) {
        // 特殊情况：窗口长度大于数组长度
        if (n < w) {
            return new int[]{-1, 0};
        }
        
        // 初始化滑动窗口：计算第一个窗口的元素和与0的个数
        int windowSum = 0;
        int zeroCount = 0;
        for (int i = 0; i < w; i++) {
            windowSum += scores[i];
            if (scores[i] == 0) {
                zeroCount++;
            }
        }
        
        // 记录最优结果
        int bestStart = -1;
        int minSum = Integer.MAX_VALUE;
        
        // 检查首个窗口是否有效
        if (zeroCount == 0) {
            minSum = windowSum;
            bestStart = 0;
        }
        
        // 滑动窗口：依次检查后续窗口
        for (int start = 1; start <= n - w; start++) {
            // 移除窗口最左边的元素
            int outVal = scores[start - 1];
            windowSum -= outVal;
            if (outVal == 0) {
                zeroCount--;
            }
            
            // 加入窗口最右边的元素
            int inVal = scores[start + w - 1];
            windowSum += inVal;
            if (inVal == 0) {
                zeroCount++;
            }
            
            // 只有当窗口内没有0时，才考虑更新最优结果
            // 使用严格小于，保证平局时选择起始位置更早的窗口
            if (zeroCount == 0 && windowSum < minSum) {
                minSum = windowSum;
                bestStart = start;
            }
        }
        
        // 如果没有找到有效窗口
        if (bestStart == -1) {
            return new int[]{-1, 0};
        }
        
        return new int[]{bestStart, minSum};
    }
}

Python

"""
华为OD机试真题 - 数据中心最佳维护窗口
"""
from typing import List


class Solution:
    def findMaintenanceWindow(self, n: int, w: int, scores: List[int]) -> List[int]:
        """核心算法：查找最佳维护窗口"""
        if n < w:
            return [-1, 0]
        
        # 初始化滑动窗口
        window_sum = sum(scores[:w])
        zero_count = scores[:w].count(0)
        
        best_start = -1
        min_sum = float('inf')
        
        if zero_count == 0:
            min_sum = window_sum
            best_start = 0
        
        # 滑动窗口
        for start in range(1, n - w + 1):
            # 更新窗口和
            window_sum += scores[start + w - 1] - scores[start - 1]
            
            # 更新0的个数
            if scores[start - 1] == 0:
                zero_count -= 1
            if scores[start + w - 1] == 0:
                zero_count += 1
            
            # 更新最优结果
            if zero_count == 0 and window_sum < min_sum:
                min_sum = window_sum
                best_start = start
        
        return [-1, 0] if best_start == -1 else [best_start, min_sum]


if __name__ == "__main__":
    # 读取输入
    n = int(input().strip())
    w = int(input().strip())
    scores = list(map(int, input().strip().split(',')))
    
    # 调用算法
    result = Solution().findMaintenanceWindow(n, w, scores)
    
    # 输出结果（逗号分隔）
    print(f"{result[0]},{result[1]}")

JavaScript

/**
 * 华为OD机试真题 - 数据中心最佳维护窗口
 */

function findMaintenanceWindow(n, w, scores) {
    if (n < w) return [-1, 0];
    
    // 初始化滑动窗口
    let windowSum = scores.slice(0, w).reduce((a, b) => a + b, 0);
    let zeroCount = scores.slice(0, w).filter(x => x === 0).length;
    
    let bestStart = -1;
    let minSum = Infinity;
    
    if (zeroCount === 0) {
        minSum = windowSum;
        bestStart = 0;
    }
    
    // 滑动窗口
    for (let start = 1; start <= n - w; start++) {
        windowSum += scores[start + w - 1] - scores[start - 1];
        if (scores[start - 1] === 0) zeroCount--;
        if (scores[start + w - 1] === 0) zeroCount++;
        
        if (zeroCount === 0 && windowSum < minSum) {
            minSum = windowSum;
            bestStart = start;
        }
    }
    
    return bestStart === -1 ? [-1, 0] : [bestStart, minSum];
}

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });

const lines = [];
rl.on('line', (line) => lines.push(line.trim()));

rl.on('close', () => {
    const n = parseInt(lines[0]);
    const w = parseInt(lines[1]);
    const scores = lines[2].split(',').map(Number);
    
    const result = findMaintenanceWindow(n, w, scores);
    console.log(result[0] + ',' + result[1]);
});

C++

#include <iostream>
#include <vector>
#include <sstream>
#include <climits>

using namespace std;

vector<int> findMaintenanceWindow(int n, int w, const vector<int>& scores) {
    if (n < w) return {-1, 0};
    
    int windowSum = 0, zeroCount = 0;
    for (int i = 0; i < w; i++) {
        windowSum += scores[i];
        if (scores[i] == 0) zeroCount++;
    }
    
    int bestStart = -1, minSum = INT_MAX;
    
    if (zeroCount == 0) {
        minSum = windowSum;
        bestStart = 0;
    }
    
    for (int start = 1; start <= n - w; start++) {
        windowSum += scores[start + w - 1] - scores[start - 1];
        if (scores[start - 1] == 0) zeroCount--;
        if (scores[start + w - 1] == 0) zeroCount++;
        
        if (zeroCount == 0 && windowSum < minSum) {
            minSum = windowSum;
            bestStart = start;
        }
    }
    
    return bestStart == -1 ? vector<int>{-1, 0} : vector<int>{bestStart, minSum};
}

int main() {
    int n, w;
    string line;
    
    getline(cin, line);
    n = stoi(line);
    getline(cin, line);
    w = stoi(line);
    getline(cin, line);
    
    // 解析逗号分隔的数组
    vector<int> scores;
    stringstream ss(line);
    string num;
    while (getline(ss, num, ',')) {
        scores.push_back(stoi(num));
    }
    
    auto result = findMaintenanceWindow(n, w, scores);
    cout << result[0] << "," << result[1] << endl;
    
    return 0;
}

Go

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <string.h>

void findMaintenanceWindow(int n, int w, int* scores, int* result) {
    if (n < w) {
        result[0] = -1;
        result[1] = 0;
        return;
    }
    
    int windowSum = 0, zeroCount = 0;
    for (int i = 0; i < w; i++) {
        windowSum += scores[i];
        if (scores[i] == 0) zeroCount++;
    }
    
    int bestStart = -1, minSum = INT_MAX;
    
    if (zeroCount == 0) {
        minSum = windowSum;
        bestStart = 0;
    }
    
    for (int start = 1; start <= n - w; start++) {
        windowSum += scores[start + w - 1] - scores[start - 1];
        if (scores[start - 1] == 0) zeroCount--;
        if (scores[start + w - 1] == 0) zeroCount++;
        
        if (zeroCount == 0 && windowSum < minSum) {
            minSum = windowSum;
            bestStart = start;
        }
    }
    
    result[0] = bestStart == -1 ? -1 : bestStart;
    result[1] = bestStart == -1 ? 0 : minSum;
}

int main() {
    int n, w;
    char line[1000000];
    
    scanf("%d", &n);
    getchar(); // consume newline
    scanf("%d", &w);
    getchar(); // consume newline
    
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    // 解析逗号分隔的数组
    int* scores = (int*)malloc(n * sizeof(int));
    char* token = strtok(line, ",");
    int i = 0;
    while (token != NULL && i < n) {
        scores[i++] = atoi(token);
        token = strtok(NULL, ",");
    }
    
    int result[2];
    findMaintenanceWindow(n, w, scores, result);
    printf("%d,%d\n", result[0], result[1]);
    
    free(scores);
    return 0;
}#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <string.h>

void findMaintenanceWindow(int n, int w, int* scores, int* result) {
    if (n < w) {
        result[0] = -1;
        result[1] = 0;
        return;
    }
    
    int windowSum = 0, zeroCount = 0;
    for (int i = 0; i < w; i++) {
        windowSum += scores[i];
        if (scores[i] == 0) zeroCount++;
    }
    
    int bestStart = -1, minSum = INT_MAX;
    
    if (zeroCount == 0) {
        minSum = windowSum;
        bestStart = 0;
    }
    
    for (int start = 1; start <= n - w; start++) {
        windowSum += scores[start + w - 1] - scores[start - 1];
        if (scores[start - 1] == 0) zeroCount--;
        if (scores[start + w - 1] == 0) zeroCount++;
        
        if (zeroCount == 0 && windowSum < minSum) {
            minSum = windowSum;
            bestStart = start;
        }
    }
    
    result[0] = bestStart == -1 ? -1 : bestStart;
    result[1] = bestStart == -1 ? 0 : minSum;
}

int main() {
    int n, w;
    char line[1000000];
    
    scanf("%d", &n);
    getchar(); // consume newline
    scanf("%d", &w);
    getchar(); // consume newline
    
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    // 解析逗号分隔的数组
    int* scores = (int*)malloc(n * sizeof(int));
    char* token = strtok(line, ",");
    int i = 0;
    while (token != NULL && i < n) {
        scores[i++] = atoi(token);
        token = strtok(NULL, ",");
    }
    
    int result[2];
    findMaintenanceWindow(n, w, scores, result);
    printf("%d,%d\n", result[0], result[1]);
    
    free(scores);
    return 0;
}

C语言

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

void findMaintenanceWindow(int n, int w, int scores[], int result[]) {
    if (n < w) {
        result[0] = -1;
        result[1] = 0;
        return;
    }

    int windowSum = 0, zeroCount = 0;
    for (int i = 0; i < w; i++) {
        windowSum += scores[i];
        if (scores[i] == 0) zeroCount++;
    }

    int bestStart = -1, minSum = INT_MAX;

    if (zeroCount == 0) {
        minSum = windowSum;
        bestStart = 0;
    }

    for (int start = 1; start <= n - w; start++) {
        windowSum += scores[start + w - 1] - scores[start - 1];
        if (scores[start - 1] == 0) zeroCount--;
        if (scores[start + w - 1] == 0) zeroCount++;

        if (zeroCount == 0 && windowSum < minSum) {
            minSum = windowSum;
            bestStart = start;
        }
    }

    if (bestStart == -1) {
        result[0] = -1;
        result[1] = 0;
    } else {
        result[0] = bestStart;
        result[1] = minSum;
    }
}

int main() {
    int n, w;
    char line[1000000];

    fgets(line, sizeof(line), stdin);
    n = atoi(line);

    fgets(line, sizeof(line), stdin);
    w = atoi(line);

    fgets(line, sizeof(line), stdin);

    int *scores = (int *)malloc(sizeof(int) * n);
    int count = 0;

    char *token = strtok(line, ",");
    while (token != NULL && count < n) {
        scores[count++] = atoi(token);
        token = strtok(NULL, ",");
    }

    int result[2];
    findMaintenanceWindow(n, w, scores, result);

    printf("%d,%d\n", result[0], result[1]);

    free(scores);
    return 0;
}

完整用例

用例1

输入：

9
2
10,5,20,10,5,15,10,5,25

用例2

输入：

5
3
0,5,0,8,12

用例3

输入：

12
4
10,2,1,0,15,0,8,3,6,12,6,9

用例4

输入：

6
2
1,2,3,4,5,6

用例5

输入：

8
3
0,0,5,6,0,7,8,0

用例6

输入：

10
3
1,0,2,0,3,0,4,5,6,7

用例7

输入：

5
5
2,3,1,5,4

用例8

输入：

7
2
1,1,0,1,1,1,1

用例9

输入：

6
1
0,5,0,5,0,5

用例10

输入：

9
3
5,5,5,5,5,5,5,5,5