题意分析

在珍珠环中找到一个长度在 $[L,U]$ 之间的子串，使其平均亮度最大。

解题思路

1、理解问题‌：首先，需要理解项链是一个环状结构，这意味着首尾相连。 2、计算平均亮度‌：对于环状项链，可以将其展开成一条直线进行处理。计算每个子串的平均亮度，即子串内所有珍珠亮度的总和除以子串的长度。 3、寻找最优解‌：通过遍历所有可能的子串，找到平均亮度最高的子串。由于项链是环状的，需要考虑从某个点开始切割到某个点结束的所有可能性。 4、为了减少计算量，可以采用滑动窗口的方法来动态地计算每个子串的平均亮度，从而找到最优解。

C++实现

cpp

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

// 求最大公约数
int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// 检查是否存在平均亮度大于等于mid的子串
bool check(const vector<int>& pearls, int L, int U, double mid) {
    int n = pearls.size();
    vector<double> prefixSum(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        prefixSum[i] = prefixSum[i - 1] + pearls[i - 1] - mid;
    }

    double minVal = 0;
    for (int r = L; r <= n; ++r) {
        if (r >= L) {
            minVal = min(minVal, prefixSum[r - L]);
        }
        if (prefixSum[r] - minVal >= 0) {
            return true;
        }
    }
    return false;
}

// 计算最大平均亮度子串
pair<int, int> findMaxAverage(const vector<int>& pearls, int L, int U) {
    int n = pearls.size();
    double left = -1000, right = 1000;
    const double eps = 1e-6;

    while (right - left > eps) {
        double mid = (left + right) / 2;
        if (check(pearls, L, U, mid)) {
            left = mid;
        } else {
            right = mid;
        }
    }

    int maxSum = 0;
    int maxLen = 0;
    for (int len = L; len <= U; ++len) {
        for (int start = 0; start < n; ++start) {
            int sum = 0;
            for (int i = 0; i < len; ++i) {
                sum += pearls[(start + i) % n];
            }
            if (sum * maxLen > maxSum * len) {
                maxSum = sum;
                maxLen = len;
            }
        }
    }

    // 化简分数
    int divisor = gcd(maxSum, maxLen);
    return {maxSum / divisor, maxLen / divisor};
}

int main() {
    int N, L, U;
    while (cin >> N >> L >> U) {
        vector<int> pearls(N);
        for (int i = 0; i < N; ++i) {
            cin >> pearls[i];
        }

        auto [numerator, denominator] = findMaxAverage(pearls, L, U);
        cout << numerator << "/" << denominator << endl;
    }

    return 0;
}