洛谷P1404 平均数
题目描述
给一个长度为 \(n\) 的数列，我们需要找出该数列的一个子串，使得子串平均数最大化，并且子串长度 \(\geq m\) 。
输入格式
第一行两个整数 \(n\) 和 \(m\)。
接下来 \(n\) 行，每行一个整数 \(a_i\)，表示序列第 \(i\) 个数字。
输出格式
一个整数，表示最大平均数的 \(1000\) 倍，如果末尾有小数，直接舍去，不要用四舍五入求整。
数据规模
对于 \(60\%\) 的数据，保证 \(m \leq n \leq 10^4\);
对于 \(100\%\) 的数据，保证 \(1 \leq a_i \leq 2000\)。
题解
朴素的思想是枚举所有的子串，找到最大平均数，时间复杂度 \(O(n^2)\)，无法通过此题。
考虑优化，本题的特殊限制条件是子串长度不得小于 \(m\) 。如何保证这一条件满足呢？只需要先找到所有长度为 \(m\) 的子串，再在这些子串的基础上向前或向后扩展即可得到所有符合要求的子串。通过枚举子串的第一个元素的位置 \(i\) 易得子串的最后一个元素位置为 \(i + m - 1\)，故可方便的在 \(O(n)\) 的复杂度内枚举长度为 \(m\) 的子串。
考虑扩展子串，如果向后扩展的同时向前扩展，则向后扩展的子串会和后续子串向前扩展的子串重合，形成枚举的重复，故只向前或向后扩展。此处采用向前扩展。优化的关键是在 \(O(\log n)\) 的复杂度内求出最优的扩展方法。显然枚举的复杂度是 \(O(n)\) 不符合要求。笔者的最初想法是使用前缀的最大平均值进行扩展，只需要 \(O(1)\) 的时间复杂度。但对于单个最高的数来说，可能选择多个较小的数的情况更优，因为两组数的并的平均值不等于两组数平均值的平均值，故作罢。那么还有什么方法可以过滤没有必要的扩展呢？
考虑二分答案。对于一个选定的基准数作为平均数的情况考虑扩展，易得以下扩展策略：
- 前缀的平均数小于基准数，舍弃前缀;
- 前缀的平均数大于等于基准数，则保留前缀。
因此，只需要在枚举长度为 \(m\) 的子串的同时用以上策略扩展即可得到基准数确定时的最优情况。二分的时间复杂度为 \(O(\log a)\)，验证的时间复杂度为 \(O(n)\)， 总时间复杂度为 \(O(n \log a)\) ，可以解决此题。
AC代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define int long long
using namespace std;
const int MAXN = 1e6 + 3;
int n, m;
double a[MAXN];
double sum = 0.0; //维护只取m个数的和
bool check(double x) {
sum = 0.0;
for (int i = 1; i <= m; i++) {
sum += a[i];
}
double ans = 0.0;
double preSum = 0.0; //维护往前延伸的最大平均数的和（分子）
double preNum = 0.0; //维护往前延伸的最大平均数的数量（分母）
for (int i = 1; i <= n - m + 1; i++) { //从m开始枚举子串的第一个数的位置
double preAvg = 0.0; //往前延伸的最大平均数
if (preNum != 0) preAvg = preSum / preNum;
if (preAvg < x) preSum = a[i - 1], preNum = 1.0; //之前的平均数达不到x，则只保留新出现的数
else preSum += a[i - 1], preNum += 1.0; //否则在保留之前的前缀的基础上加上新出现的数
ans = max(ans, max((sum + preSum) / ((double)m + preNum), sum / (double)m)); //更新答案
sum -= a[i]; //减去子串的第一个数
sum += a[i + m]; //加上新出现的一个数
}
return ans >= x;
}
signed main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
double l = 0, r = 2000, mid;
while (l + 1e-5 < r) {
mid = (l + r) / 2.0;
if (check (mid)) l = mid;
else r = mid;
}
cout << (int)(r * 1000.0) << '\n';
return 0;
}