返回目录

题目描述

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

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

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

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

输入描述

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

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

输出描述

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

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

示例：

题目解析

本题需要求出第二行输入的所有区间，比如0 1 2 3 4区间有

• 0
• 0\~1, 1
• 0\~2, 1\~2, 2
• 0\~3, 1\~3, 2\~3, 3
• 0\~4, 1\~4, 2\~4, 3\~4, 4

我们需要计算出这些区间的平均失败率容忍值averageLost，和第一行输入的minAverageLost比较，

如果averageLost > minAverageLost，则不考虑

如果averageLost <= minAverageLost，则考虑

最后将考虑中所有区间进行比较，保留最长的，注意可能有多个相同时间长度的。

这里模拟出上面区间，很明显需要使用双重for

for(let i=0; i<arr.length; i++) { // 区间右边界，包含
        for(let j=0; j<i; j++) {// 区间左边界，不包含

        }
}

这里，我们为了避免陷入遍历i到j，来计算区间[i, j]的总和，我们可以事先定义一个dp数组，dp[i]表示以0\~i区间的和（即前缀和）。

因此[j, i]区间总和的计算就是dp[j] - dp[i-1]。

Python算法源码

def get_result(nums, min_average_lost):
    n = len(nums)

    pre_sum = [0] * (n + 1)
    for i in range(1, n + 1):
        pre_sum[i] = pre_sum[i - 1] + nums[i - 1]

    ans = []
    max_len = 0

    for i in range(n):
        for j in range(i + 1, n + 1):
            # sum 是 区间 [i, j-1] 的和
            sum_val = pre_sum[j] - pre_sum[i]
            length = j - i
            lost = length * min_average_lost

            if sum_val <= lost:
                if length >= max_len:
                    if length > max_len:
                        ans = []
                    ans.append((i, j - 1))
                    max_len = length

    if not ans:
        return "NULL"
  
    ans.sort(key=lambda x: x[0])
    return " ".join([f"{arr[0]}-{arr[1]}" for arr in ans])


if __name__ == "__main__":
    min_average_lost = int(input())
    nums = list(map(int, input().split()))

    print(get_result(nums, min_average_lost))

C算法源码

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

#define MAX_SIZE 100

// 定义一个结构体来存储区间
struct Interval {
    int start; // 区间起始位置
    int end;   // 区间结束位置
};

// 函数用于打印 Interval 结构体数组
void printIntervals(struct Interval arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d-%d ", arr[i].start, arr[i].end);
    }
    printf("\n");
}

int main() {
    int n;
    // 读取 n 的值
    scanf("%d", &n);
    // 读取换行符
    getchar();

    char input[MAX_SIZE];
    // 读取输入行
    fgets(input, sizeof(input), stdin);

    int ints[MAX_SIZE];
    int intsSize = 0;

    // 将输入行进行标记化并将标记转换为整数
    char *token = strtok(input, " ");
    while (token != NULL) {
        ints[intsSize++] = atoi(token);
        token = strtok(NULL, " ");
    }

    int maxLen = 0;
    struct Interval list[MAX_SIZE];
    int listSize = 0;

    int len = intsSize;
    // 遍历所有可能的子数组
    for (int i = 0; i < len; i++) {
        int count = ints[i];
        for (int j = i; j < len; j++) {
            if (i != j) {
                count += ints[j];
            }
            int numLen = j - i + 1;
            // 检查子数组中元素的和是否在限制内
            if (count <= numLen * n) {
                if (numLen > maxLen) {
                    // 更新最大长度并清空列表
                    maxLen = numLen;
                    listSize = 0;
                    list[listSize].start = i;
                    list[listSize].end = j;
                    listSize++;
                } else if (numLen == maxLen) {
                    // 将区间添加到列表中
                    list[listSize].start = i;
                    list[listSize].end = j;
                    listSize++;
                }
            }
        }
    }

    if (listSize == 0) {
        printf("NULL\n");
    } else {
        // 打印具有最大长度的区间
        printIntervals(list, listSize);
    }

    return 0;
}

Java算法源码

import java.util.Scanner;
import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 读取 minAverageLost 的值
        int minAverageLost = scanner.nextInt();
        scanner.nextLine(); // 读取换行符

        // 读取 nums 数组的值
        String[] numsStr = scanner.nextLine().split(" ");
        int[] nums = new int[numsStr.length];
        for (int i = 0; i < numsStr.length; i++) {
            nums[i] = Integer.parseInt(numsStr[i]);
        }

        int n = nums.length;

        int[] preSum = new int[n + 1];
        // 计算前缀和数组 preSum
        for (int i = 1; i <= n; i++) {
            preSum[i] = preSum[i - 1] + nums[i - 1];
        }

        ArrayList<int[]> ans = new ArrayList<>();
        int maxLen = 0;

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j <= n; j++) {
                // sum 是 区间 [i, j-1] 的和
                int sum = preSum[j] - preSum[i];
                int len = j - i;
                int lost = len * minAverageLost;

                // 检查 sum 是否小于等于 lost
                if (sum <= lost) {
                    // 更新最大长度区间列表
                    if (len >= maxLen) {
                        if (len > maxLen) {
                            ans.clear();
                        }
                        ans.add(new int[]{i, j - 1});
                        maxLen = len;
                    }
                }
            }
        }

        // 输出结果
        if (ans.isEmpty()) {
            System.out.println("NULL");
        } else {
            StringBuilder result = new StringBuilder();
            for (int[] interval : ans) {
                result.append(interval[0]).append("-").append(interval[1]).append(" ");
            }
            System.out.println(result.toString().trim());
        }
    }
}