一个长度为n个序列a, 定义ai为第i个元素的价值。现在需要找出序列中最有价值的"段落"。段落的定义是长度在[S, T]之间的连续序列。最有价值段落是指平均值最大的段落。
段落的平均值等于段落总价值除以段落长度。
第一行一个整数n, 表示序列长度。 第二行两个整数S和T,表示段落长度的范围,在[S, T]之间。 第三行到第n+2行,每行一个整数表示每个元素的价值。
一个实数,保留3位小数,表示最优段落的平均值。
3 2 2 3 -1 2
1.000
#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;
int main() {
int n;
cin >> n;
int S, T;
cin >> S >> T;
vector<int> values(n);
for (int i = 0; i < n; i++) {
cin >> values[i];
}
double maxAverage = -1e9;
for (int len = S; len <= T; len++) {
if (len > n) continue;
double currentSum = 0;
for (int i = 0; i < len; i++) {
currentSum += values[i];
}
for (int start = 0; start <= n - len; start++) {
double currentAverage = currentSum / len;
maxAverage = max(maxAverage, currentAverage);
if (start + len < n) {
currentSum += values[start + len] - values[start];
}
}
}
cout << fixed << setprecision(3) << maxAverage << endl;
return 0;
}