华为od机试真题：查找接口成功率最优时间段(C语言)

2024华为OD机试（C卷+D卷）最新题库【超值优惠】Java/Python/C++合集

题目描述

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

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

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

如果未找到则直接返回NULL。

输入描述

有两行内容，

第一行为 minAverageLost，

第二行为数组，数组元素通过空格(" ")分隔,

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

输出描述

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

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

示例1

输入：
1
0 1 2 3 4

输出：
0-2

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

示例2

输入：
2
0 0 100 2 2 99 0 2

输出：
0-1 3-4 6-7

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

题解

题目类型

这道题属于 前缀和 与 双指针 结合的题目，题目要求通过计算一个时间段的平均失败率来找到符合条件的最长时间段。

解题思路

1. 前缀和计算：
   • 通过前缀和数组 psum，我们可以快速计算任意区间 [l, r] 的总失败率。这个思想在区间求和问题中非常常见。
   • psum[i] 表示数组前 i 个元素的和，那么区间 [l, r] 的和为 psum[r + 1] - psum[l]。
2. 双层循环：
   • 外层循环遍历每个可能的起点 l，内层循环检查从 l 开始的每个可能的终点 r。
   • 对于每个区间 [l, r]，我们计算其总失败率和长度，检查该区间的平均失败率是否小于等于 minAverageLost。如果满足条件，我们记录下这个区间，并更新最长区间长度。
3. 处理多个最长时间段：
   • 如果找到更长的时间段，就更新结果并清除之前的短时间段。
   • 如果找到和当前最长时间段相同长度的段，则继续记录。
4. 最终输出：
   • 遍历所有符合条件的区间，按要求输出这些区间的起止下标对。

代码大致描述

• 输入解析：首先读取 minAverageLost 和数组数据，通过前缀和的方式记录失败率的累积和。
• 双层循环：从左到右遍历所有区间，并用前缀和快速计算任意区间的失败率。如果该区间平均失败率满足条件，则更新最长区间长度，并记录结果。
• 输出结果：按照格式输出满足条件的最长区间下标对。

时间复杂度

• 时间复杂度：外层循环从数组的每一个起点开始，内层循环检查从该起点出发的每一个终点。因此，总的时间复杂度为 O(n^2)，其中 n 是数组的长度，最多 100 个元素，所以能够接受。
• 空间复杂度：需要额外的前缀和数组 O(n)，因此空间复杂度为 O(n)。

C

#include <stdio.h>

#define N 105

// psum 记录失败值的前缀和
int psum[N];
int n = 0;

// 记录结果区间
int result[N][2];
int rlen = 0;

int main() {
    int minAverageLost;
    scanf("%d", &minAverageLost);

    for (int lost;;) {
        scanf("%d", &lost);
        psum[n + 1] = psum[n] + lost;
        n++;

        if (getchar() == '\n') break;
    }

    int max_length = 1;
    for (int l = 0; l < n; l++) {
        for (int r = l + max_length - 1; r < n; r++) {
            int length = r - l + 1;
            // psum[r+1] - pusm[l] 表示从 [l, r] 的接口总失败率
            if (psum[r + 1] - psum[l] <= minAverageLost * length) {
                // 碰到数组更长的时间段
                if (length > max_length) {
                    max_length = length;
                    // 之前的结果都不符合情况，rlen = 0 表示之前的结果都不需要
                    rlen = 0;
                }

                // 记录区间结果
                result[rlen][0] = l;
                result[rlen][1] = r;
                rlen++;
            }
        }
    }

    // 打印结果
    for (int i = 0; i < rlen; i++) {
        printf("%d-%d", result[i][0], result[i][1]);
        printf((i + 1 == rlen) ? "\n" : " ");
    }

    return 0;
}

前缀和

前缀和是一种常用的算法技巧，用于快速计算一个数组的某个子数组（连续元素）的总和。通过预先计算好数组的累积和，可以在常数时间内得到任何一个子数组的和。

前缀和的基本思想

• 定义前缀和数组 Psum，其中 Psum[i] 表示原数组前 i 个元素的累加和。
• 如果我们想计算原数组中某一段连续子数组的和，比如区间 [l, r]，我们只需要通过 Psum[r] - Psum[l-1] 就可以得到区间 [l, r] 的和，而不用每次都重新计算。

举个栗子

假设我们有一个数组 A，值为：

A = [3, 1, 4, 1, 5]

我们要计算前缀和数组 Psum：

Psum[0] = 0  (为了方便计算，把Psum[0]设为0)
Psum[1] = A[0] = 3
Psum[2] = A[0] + A[1] = 3 + 1 = 4
Psum[3] = A[0] + A[1] + A[2] = 3 + 1 + 4 = 8
Psum[4] = A[0] + A[1] + A[2] + A[3] = 3 + 1 + 4 + 1 = 9
Psum[5] = A[0] + A[1] + A[2] + A[3] + A[4] = 3 + 1 + 4 + 1 + 5 = 14

最终的前缀和数组为：

Psum = [0, 3, 4, 8, 9, 14]

如何使用前缀和计算区间和

现在，如果我们想计算数组 A 中某个区间的和，比如区间 [1, 3]（即子数组 [1, 4, 1]），我们只需要：

区间 [1, 3] 的和 = Psum[4] - Psum[1] = 9 - 3 = 6

这比直接遍历并相加数组的元素要快得多，因为我们只需要两个查找和一次减法操作。

总结

前缀和通过提前计算累积和，能够在 O(1) 的时间内计算任意连续子数组的和，大大提升了性能。

整理题解不易， 如果有帮助到您，请给点个赞 ‍❤️‍ 收藏 ⭐和小红花🌹，让更多的人看到。🙏🙏🙏