E卷-刷题笔记合集🔗

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

问题描述

K小姐正在分析某服务之间交换接口的成功率。她将一段时间内的接口失败率表示为一个数组，数组中每个元素都是单位时间内的失败率数值，取值范围为 到 的整数。

给定一个数值 ，表示某个时间段内可以容忍的平均失败率，即平均失败率小于等于 。K小姐希望找出数组中满足条件的最长连续时间段，如果找不到则返回 NULL。

输入格式

输入包含两行内容：

第一行为一个整数 ，表示可以容忍的平均失败率。

第二行为一个整数数组，表示各个时间段的失败率，数组元素之间用空格分隔。

• 和数组中元素的取值范围均为 到 的整数。
• 数组元素的个数不超过 。

输出格式

输出满足平均失败率小于等于 的最长连续时间段的数组下标对，格式为 beginIndex-endIndex（下标从 开始）。

如果存在多个最长时间段，则输出多个下标对，下标对之间用空格分隔，并按照下标对的起始下标从小到大排序。

如果不存在满足条件的时间段，则输出 NULL。

样例输入

1
0 1 2 3 4

样例输出

0-2

样例输入

2
0 0 100 2 2 99 0 2

样例输出

0-1 3-4 6-7

数据范围

• 
• 数组元素
• 数组长度

题解

本题可以使用前缀和结合双重循环来解决。

首先计算数组的前缀和，即 表示数组前 个元素的和。这样可以方便地计算任意区间的元素和。

然后使用双重循环枚举所有可能的区间 ，计算该区间的元素和以及区间长度。如果区间平均值小于等于 ，则更新最长区间长度以及对应的区间下标。

最后，将满足条件的最长区间下标对按要求格式输出即可。如果不存在满足条件的区间，则输出 NULL。

时间复杂度为 ，空间复杂度为 ，其中 为数组长度。

参考代码

• Cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int minAvg;
    cin >> minAvg;
    
    vector<int> nums;
    int x;
    while (cin >> x) {
        nums.push_back(x);
    }
    
    int n = nums.size();
    vector<int> preSum(n + 1);
    for (int i = 1; i <= n; i++) {
        preSum[i] = preSum[i - 1] + nums[i - 1];
    }
    
    vector<pair<int, int>> ans;
    int maxLen = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j <= n; j++) {
            int sum = preSum[j] - preSum[i];
            int len = j - i;
            int lost = len * minAvg;
            
            if (sum <= lost) {
                if (len > maxLen) {
                    ans.clear();
                    ans.emplace_back(i, j - 1);
                    maxLen = len;
                } else if (len == maxLen) {
                    ans.emplace_back(i, j - 1);
                }
            }
        }
    }
    
    if (ans.empty()) {
        cout << "NULL" << endl;
    } els