华为OD机考双机位C卷- 查找接口成功率最优时间段

算法大师

215人浏览 · 2026-06-04 23:33:38

算法大师 · 2026-06-04 23:33:38 发布

查找接口成功率最优时间段

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

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

题目描述

服务之间交换的接口成功率作为服务调用关键质量特性，某个时间段内的接口失败率使用一个数组表示，

数组中每个元素都是单位时间内失败率数值，数组中的数值为0~100的整数，

给定一个数值(minAverageLost)表示某个时间段内平均失败率容忍值，即平均失败率小于等于minAverageLost，

找出数组中最长时间段，如果未找到则直接返回NULL。

输入描述

输入有两行内容，第一行为{minAverageLost}，第二行为{数组}，数组元素通过空格(” “)分隔，

minAverageLost及数组中元素取值范围为0~100的整数，数组元素的个数不会超过100个。

输出描述

找出平均值小于等于minAverageLost的最长时间段，输出数组下标对，格式{beginIndex}-{endIndx}(下标从0开始)，

如果同时存在多个最长时间段，则输出多个下标对且下标对之间使用空格(” “)拼接，多个下标对按下标从小到大排序。

示例1

输入

1
0 1 2 3 4

输出

0-2

说明

输入解释：minAverageLost=1，数组[0, 1, 2, 3, 4]前3个元素的平均值为1，因此数组第一个至第三个数组下标，即0-2

示例2

输入

2
0 0 100 2 2 99 0 2

输出

0-1 3-4 6-7

说明

输入解释：minAverageLost=2，数组[0, 0, 100, 2, 2, 99, 0, 2]通过计算小于等于2的最长时间段为：数组下标为0-1即[0, 0]，数组下标为3-4即[2, 2]，数组下标为6-7即[0, 2]，这三个部分都满足平均值小于等于2的要求，因此输出0-1 3-4 6-7

解题思路：最长满足平均失败率的时间段

这道题的核心是寻找数组中最长的连续子数组，要求该子数组的平均值小于等于给定的容忍阈值 minAverageLost。

解题步骤

前缀和预处理：
- 首先计算数组的前缀和，这样可以在O(1)时间内计算出任意区间的元素和。
- 前缀和数组 prefixSum[i] 表示原数组从索引0到i的所有元素之和。
枚举所有可能的区间：
- 使用两重循环遍历所有可能的起始位置和结束位置。
- 对于每个区间 [start, end]：
  - 通过前缀和快速计算该区间的元素和：sum = prefixSum[end] - (start > 0 ? prefixSum[start-1] : 0)
  - 计算区间长度：length = end - start + 1
  - 判断该区间的平均值是否满足条件：sum / length <= minAverageLost
    （实际实现中，为避免浮点数比较，可转化为 sum <= length * minAverageLost）
记录最长满足条件的区间：
- 如果当前区间满足条件且长度大于之前记录的最长区间，更新最长区间记录。
- 如果当前区间满足条件且长度等于当前记录的最长区间，将该区间添加到结果集。
输出结果：
- 如果没有找到满足条件的区间，输出 “NULL”。
- 否则，按照起始索引排序后输出所有最长区间。

C++

#include <iostream>
#include <vector>
#include <sstream>
#include <algorithm>

using namespace std;

int main() {
    // 容忍的平均失败率
    int toleratedAverageLoss;
    cin >> toleratedAverageLoss;

    // 读取失败率数组
    vector<int> failureRates;
    string line;
    getline(cin >> ws, line);
    istringstream iss(line);
    int num;
    while (iss >> num) {
        failureRates.push_back(num);
    }

    int arrayLength = failureRates.size();

    // 创建一个累积和数组，用于快速计算任意时间段的失败率总和
    vector<int> cumulativeSum(arrayLength);
    cumulativeSum[0] = failureRates[0];
    for (int i = 1; i < arrayLength; i++) cumulativeSum[i] = cumulativeSum[i - 1] + failureRates[i];

    // 存储满足条件的时间段的开始和结束索引
    vector<pair<int, int>> validPeriods;
    int maxLength = 0;
    for (int start = 0; start < arrayLength; start++) {
        for (int end = start; end < arrayLength; end++) {
            int sum = start == 0 ? cumulativeSum[end] : cumulativeSum[end] - cumulativeSum[start - 1];
            int length = end - start + 1;
            int toleratedLoss = length * toleratedAverageLoss;

            // 如果这个时间段的平均失败率小于等于容忍的平均失败率
            if (sum <= toleratedLoss) {
                // 如果这个时间段比之前找到的时间段更长，清空结果列表并添加这个时间段
                if (length > maxLength) {
                    validPeriods.clear();
                    validPeriods.push_back({start, end});
                    maxLength = length;
                } 
                // 如果这个时间段和之前找到的最长时间段一样长，添加这个时间段
                else if (length == maxLength) {
                    validPeriods.push_back({start, end});
                }
            }
        }
    }

    // 如果没有找到满足条件的时间段，输出"NULL"
    if (validPeriods.empty()) {
        cout << "NULL" << endl;
    } 
    // 否则，输出所有满足条件的时间段
    else {
        sort(validPeriods.begin(), validPeriods.end());

        for (auto& period : validPeriods) {
            cout << period.first << "-" << period.second << " ";
        }
        cout << endl;
    }

    return 0;
}

JavaScript

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

 

readline.on('line', tolerated => {
 const toleratedAverageLoss = parseInt(tolerated);
  readline.on('line', rates => {a
    const failureRates = rates.split(' ').map(Number);
 
    const arrayLength = failureRates.length;

    // 创建一个累积和数组，用于快速计算任意时间段的失败率总和
    const cumulativeSum = new Array(arrayLength);
    cumulativeSum[0] = failureRates[0];
    for (let i = 1; i < arrayLength; i++) cumulativeSum[i] = cumulativeSum[i - 1] + failureRates[i];

    // 存储满足条件的时间段的开始和结束索引
    let validPeriods = [];
    let maxLength = 0;
    for (let start = 0; start < arrayLength; start++) {
      for (let end = start; end < arrayLength; end++) {
        const sum = start === 0 ? cumulativeSum[end] : cumulativeSum[end] - cumulativeSum[start - 1];
        const length = end - start + 1;
        const toleratedLoss = length * toleratedAverageLoss;

        // 如果这个时间段的平均失败率小于等于容忍的平均失败率
        if (sum <= toleratedLoss) {
          // 如果这个时间段比之前找到的时间段更长，清空结果列表并添加这个时间段
          if (length > maxLength) {
            validPeriods = [];
            validPeriods.push([start, end]);
            maxLength = length;
          } 
          // 如果这个时间段和之前找到的最长时间段一样长，添加这个时间段
          else if (length === maxLength) {
            validPeriods.push([start, end]);
          }
        }
      }
    }

    // 如果没有找到满足条件的时间段，输出"NULL"
    if (validPeriods.length === 0) {
      console.log("NULL");
    } 
    // 否则，输出所有满足条件的时间段
    else {
      validPeriods.sort((a, b) => a[0] - b[0]);

      console.log(validPeriods.map(period => period.join('-')).join(' '));
    }
  });
});

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
import java.util.StringJoiner;

public class Main {
  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);

    // 容忍的平均失败率
    int toleratedAverageLoss = Integer.parseInt(scanner.nextLine());

    // 读取失败率数组
    Integer[] failureRates =
        Arrays.stream(scanner.nextLine().split(" ")).map(Integer::parseInt).toArray(Integer[]::new);

    int arrayLength = failureRates.length;

    // 创建一个累积和数组，用于快速计算任意时间段的失败率总和
    int[] cumulativeSum = new int[arrayLength];
    cumulativeSum[0] = failureRates[0];
    for (int i = 1; i < arrayLength; i++) cumulativeSum[i] = cumulativeSum[i - 1] + failureRates[i];

    // 存储满足条件的时间段的开始和结束索引
    ArrayList<Integer[]> validPeriods = new ArrayList<>();
    int maxLength = 0;
    for (int start = 0; start < arrayLength; start++) {
      for (int end = start; end < arrayLength; end++) {
        int sum = start == 0 ? cumulativeSum[end] : cumulativeSum[end] - cumulativeSum[start - 1];
        int length = end - start + 1;
        int toleratedLoss = length * toleratedAverageLoss;

        // 如果这个时间段的平均失败率小于等于容忍的平均失败率
        if (sum <= toleratedLoss) {
          // 如果这个时间段比之前找到的时间段更长，清空结果列表并添加这个时间段
          if (length > maxLength) {
            validPeriods = new ArrayList<>();
            validPeriods.add(new Integer[] {start, end});
            maxLength = length;
          } 
          // 如果这个时间段和之前找到的最长时间段一样长，添加这个时间段
          else if (length == maxLength) {
            validPeriods.add(new Integer[] {start, end});
          }
        }
      }
    }

    // 如果没有找到满足条件的时间段，输出"NULL"
    if (validPeriods.size() == 0) {
      System.out.println("NULL");
    } 
    // 否则，输出所有满足条件的时间段
    else {
      validPeriods.sort((a, b) -> a[0] - b[0]);

      StringJoiner sj = new StringJoiner(" ");
      for (Integer[] period : validPeriods) sj.add(period[0] + "-" + period[1]);
      System.out.println(sj.toString());
    }
  }
}

Python

# 容忍的平均失败率
toleratedAverageLoss = int(input())

# 读取失败率数组
failureRates = list(map(int, input().split()))

arrayLength = len(failureRates)

# 创建一个累积和数组，用于快速计算任意时间段的失败率总和
cumulativeSum = [0] * arrayLength
cumulativeSum[0] = failureRates[0] 
for i in range(1, arrayLength):
    cumulativeSum[i] = cumulativeSum[i - 1] + failureRates[i]

# 存储满足条件的时间段的开始和结束索引
validPeriods = []
maxLength = 0
for start in range(arrayLength):
    for end in range(start, arrayLength):
        sum = cumulativeSum[end] if start == 0 else cumulativeSum[end] - cumulativeSum[start - 1]
        length = end - start + 1
        toleratedLoss = length * toleratedAverageLoss

        # 如果这个时间段的平均失败率小于等于容忍的平均失败率
        if sum <= toleratedLoss:
            # 如果这个时间段比之前找到的时间段更长，清空结果列表并添加这个时间段
            if length > maxLength:
                validPeriods = []
                validPeriods.append((start, end))
                maxLength = length
            # 如果这个时间段和之前找到的最长时间段一样长，添加这个时间段
            elif length == maxLength:
                validPeriods.append((start, end))

# 如果没有找到满足条件的时间段，输出"NULL"
if len(validPeriods) == 0:
    print("NULL")
# 否则，输出所有满足条件的时间段
else:
    validPeriods.sort()

    print(' '.join(f'{start}-{end}' for start, end in validPeriods))

GO

package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
	"strings"
)

func main() {
	var scanner = bufio.NewScanner(os.Stdin)
	
	// 读取容忍的平均失败率
	scanner.Scan()
	toleratedAverageLoss, _ := strconv.Atoi(scanner.Text())
	
	// 读取失败率数组
	scanner.Scan()
	failureRatesStr := strings.Split(scanner.Text(), " ")
	failureRates := make([]int, len(failureRatesStr))
	for i, s := range failureRatesStr {
		failureRates[i], _ = strconv.Atoi(s)
	}
	
	arrayLength := len(failureRates)
	
	// 创建一个累积和数组，用于快速计算任意时间段的失败率总和
	cumulativeSum := make([]int, arrayLength)
	cumulativeSum[0] = failureRates[0]
	for i := 1; i < arrayLength; i++ {
		cumulativeSum[i] = cumulativeSum[i-1] + failureRates[i]
	}
	
	// 存储满足条件的时间段的开始和结束索引
	type Period struct {
		Start int
		End   int
	}
	
	validPeriods := []Period{}
	maxLength := 0
	
	for start := 0; start < arrayLength; start++ {
		for end := start; end < arrayLength; end++ {
			var sum int
			if start == 0 {
				sum = cumulativeSum[end]
			} else {
				sum = cumulativeSum[end] - cumulativeSum[start-1]
			}
			
			length := end - start + 1
			toleratedLoss := length * toleratedAverageLoss
			
			// 如果这个时间段的平均失败率小于等于容忍的平均失败率
			if sum <= toleratedLoss {
				// 如果这个时间段比之前找到的时间段更长，清空结果列表并添加这个时间段
				if length > maxLength {
					validPeriods = []Period{}
					validPeriods = append(validPeriods, Period{Start: start, End: end})
					maxLength = length
				} else if length == maxLength {
					// 如果这个时间段和之前找到的最长时间段一样长，添加这个时间段
					validPeriods = append(validPeriods, Period{Start: start, End: end})
				}
			}
		}
	}
	
	// 如果没有找到满足条件的时间段，输出"NULL"
	if len(validPeriods) == 0 {
		fmt.Println("NULL")
	} else {
		// 否则，输出所有满足条件的时间段
		sort.Slice(validPeriods, func(i, j int) bool {
			return validPeriods[i].Start < validPeriods[j].Start
		})
		
		var result []string
		for _, period := range validPeriods {
			result = append(result, fmt.Sprintf("%d-%d", period.Start, period.End))
		}
		
		fmt.Println(strings.Join(result, " "))
	}
}

C语言

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

int main() {
    // 容忍的平均失败率
    int toleratedAverageLoss;
    scanf("%d", &toleratedAverageLoss);

    // 读取失败率数组
    int failureRates[100];
    int arrayLength = 0;
    while (scanf("%d", &failureRates[arrayLength]) == 1) {
        arrayLength++;
    }

    // 创建一个累积和数组，用于快速计算任意时间段的失败率总和
    int cumulativeSum[100] = {0};
    cumulativeSum[0] = failureRates[0];
    for (int i = 1; i < arrayLength; i++) {
        cumulativeSum[i] = cumulativeSum[i - 1] + failureRates[i];
    }

    // 存储满足条件的时间段的开始和结束索引
    int validPeriods[100][2];
    int validPeriodCount = 0;
    int maxLength = 0;
    for (int start = 0; start < arrayLength; start++) {
        for (int end = start; end < arrayLength; end++) {
            int sum = start == 0 ? cumulativeSum[end] : cumulativeSum[end] - cumulativeSum[start - 1];
            int length = end - start + 1;
            int toleratedLoss = length * toleratedAverageLoss;

            // 如果这个时间段的平均失败率小于等于容忍的平均失败率
            if (sum <= toleratedLoss) {
                // 如果这个时间段比之前找到的时间段更长，清空结果列表并添加这个时间段
                if (length > maxLength) {
                    validPeriodCount = 0;
                    validPeriods[validPeriodCount][0] = start;
                    validPeriods[validPeriodCount][1] = end;
                    validPeriodCount++;
                    maxLength = length;
                } 
                // 如果这个时间段和之前找到的最长时间段一样长，添加这个时间段
                else if (length == maxLength) {
                    validPeriods[validPeriodCount][0] = start;
                    validPeriods[validPeriodCount][1] = end;
                    validPeriodCount++;
                }
            }
        }
    }

    // 如果没有找到满足条件的时间段，输出"NULL"
    if (validPeriodCount == 0) {
        printf("NULL\n");
    } 
    // 否则，输出所有满足条件的时间段
    else {
        for (int i = 0; i < validPeriodCount; i++) {
            if (i > 0) printf(" ");
            printf("%d-%d", validPeriods[i][0], validPeriods[i][1]);
        }
        printf("\n");
    }

    return 0;
}

完整用例

用例1

1
0 1 2 3 4

用例2

2
0 0 100 2 2 99 0 2

用例3

3
1 2 3 4 5 6 7 8 9 10

用例4

10
10 20 30 40 50 60 70 80 90 100

用例5

50
10 20 30 40 50 60 70 80 90 100

用例6

100
10 20 30 40 50 60 70 80 90 100

用例7

0
0 0 0 0 0 0 0 0 0 0

用例8

100
100 100 100 100 100 100 100 100 100 100

用例9

50
100 100 100 100 100 100 100 100 100 100

用例10

0
100 100 100 100 100 100 100 100 100 100

fengmian

AtomGit开源社区

AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。

更多推荐

海外动态代理行业彻底换代，AI 数据时代新标准已到来

AtomGit开源社区

2026年SEO+GEO优化指南：搜索排名机制解析与实用工具推荐

AtomGit开源社区

2026年论文写作AI哪个好用？7款工具实测对比，轻松拿捏

AtomGit开源社区

所有评论(0)

查看更多评论

算法大师

@banxia_frontend

已为社区贡献7条内容

华为OD机考双机位C卷- 查找接口成功率最优时间段

算法大师

查找接口成功率最优时间段

题目描述

输入描述

输出描述

示例1

示例2

解题思路：最长满足平均失败率的时间段

解题步骤

C++

JavaScript

Java

Python

GO

C语言

完整用例

用例1

用例2

用例3

用例4

用例5

用例6

用例7

用例8

用例9

用例10

文章目录

所有评论(0)

温馨提示：您尚未绑定手机号

算法大师