最大平均数
题目描述
给定长度为 $n$ 的整数数组 $a=(a_1,\dots,a_n)$，且每个数均为 $6$ 的倍数。对于 $1 \le i < j \le n$，定义 $f(i,j) = \max_{\, i \leq l < r \leq j} \frac{a_l + a_{l+1} + \cdots + a_r}{r - l + 1}$
即 $f(i,j)$ 表示区间 $[i,j]$ 内所有长度至少为 $2$ 的连续子区间的平均值的最大值。
请计算 $\sum_{1\le i < j\le n} f(i,j)$。
可以证明上述和为整数。
输入描述:
第一行包含一个整数 $n\ (2 \le n \le 5 \times 10^3)$。
第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n, \ ( 1 \le a_i\le 10^9 )$ 且每个 $a_i$ 是 $6$ 的倍数。
输出描述:
输出一个整数，表示 $\sum_{1\le i < j\le n} f(i,j)$ 的值。
示例1
输入
2
6 12输出
9示例2
输入
5
6 12 18 12 6输出
138
解题思路
$a_i$ 是 $6$ 的倍数这个条件很诡异，以为有什么奇奇怪怪的做法，实际上这条件是用来保证结果是整数。不过这道题确实有个很难想到的做法，感觉如果不知道这个结论的话，赛时只能硬猜了。
先给出一个容易想到的做法。对于区间 $[l,r]$ 内的元素 $a_l, a_{l+1}, \dots, a_r$，要找到它的最大平均数子数组，最直接的方法是枚举所有长度至少为 $2$ 的子数组，计算平均值后取最大值。但这种纯暴力显然会超时。注意到，如果我们已经求出了区间 $[l-1,r]$ 的最大平均数子数组，那么在处理 $[l,r]$ 时，$[l+1,r]$ 子区间的结果是可以复用的。换句话说，不同区间间存在重叠子问题，因此可以考虑用 dp 来优化。
定义 $f(l,r)$ 表示区间 $[l,r]$ 的最大平均数子数组的平均值。长度小于 $r-l+1$ 的最优子数组一定落在 $[l+1,r]$ 或 $[l,r-1]$ 内，而长度正好为 $r-l+1$ 的子数组就是该区间本身，其平均值为 $\frac{a_l + a_{l+1} + \dots + a_r}{r-l+1}$。因此有状态转移方程 $$f(l,r) = \max\left\{ f(l+1,r),\ f(l,r-1),\ \frac{\sum_{t=l}^r a_t}{r-l+1} \right\}$$
计算过程中涉及浮点运算，为保证精度可以使用 long double。
AC 代码如下，时间复杂度为 $O(n^2)$：
#include <bits/stdc++.h>
using namespace std;typedef long long LL;const int N = 5e3 + 5;LL s[N];
long double f[N][N];int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin >> n;for (int i = 1; i <= n; i++) {cin >> s[i];s[i] += s[i - 1];}for (int len = 2; len <= n; len++) {for (int i = 1; i + len - 1 <= n; i++) {int j = i + len - 1;f[i][j] = max(f[i][j - 1], f[i + 1][j]);f[i][j] = max(f[i][j], (long double)(s[j] - s[i - 1]) / (j - i + 1));}}LL ret = 0;for (int i = 1; i <= n; i++) {for (int j = i + 1; j <= n; j++) {ret += LL(round(f[i][j]));}}cout << ret;return 0;
}接下来是正解。先给出结论：最大平均数子数组的长度只可能是 $2$ 或 $3$。因此在每个区间中，我们只需检查所有长度为 $2$ 与 $3$ 的子数组的平均值即可。由于 $6 \mid a_i$，这些平均值都会是整数。下面给出证明思路（部分参考 Gemini）。
设数组 $a$ 长度 $n \ge 4$，将其划分为左右两部分 $a_1 \dots a_k$ 和 $a_{k+1} \dots a_n$，其中 $2 \le k \le n-2$。我们证明至少有一部分的最大平均数子数组的均值大于或等于整个 $a$ 的均值。要求 $n \ge 4$ 的原因是保证划分后两部分的子数组都能包含至少 $2$ 个元素。
反证法，假设 $a$ 的平均值 $\tfrac{\sum\limits_{i=1}^{n}{a_i}}{n}$ 大于两部分各自的最大平均数子数组的均值，那么一定有 $\tfrac{\sum_{i=1}^{k} a_i}{k} < \tfrac{\sum_{i=1}^{n} a_i}{n}$ 以及 $\tfrac{\sum_{i=k+1}^{n} a_i}{n-k} < \tfrac{\sum_{i=1}^{n} a_i}{n}$。又因为 $$\frac{\sum\limits_{i=1}^{n}{a_i}}{n} = \frac{\sum\limits_{i=1}^{k}{a_i} + \sum\limits_{i=k+1}^{n}{a_i}}{n} = \frac{k\frac{\sum\limits_{i=1}^{k}{a_i}}{k} + (n-k)\frac{\sum\limits_{i=k+1}^{n}{a_i}}{n-k}}{n}$$
将上述不等式代入会得到 $$\frac{\sum\limits_{i=1}^{n}{a_i}}{n} = \frac{k\frac{\sum\limits_{i=1}^{k}{a_i}}{k} + (n-k)\frac{\sum\limits_{i=k+1}^{n}{a_i}}{n-k}}{n} < \frac{k\frac{\sum\limits_{i=1}^{n}{a_i}}{n} + (n-k)\frac{\sum\limits_{i=1}^{n}{a_i}}{n}}{n} = \frac{\sum\limits_{i=1}^{n}{a_i}}{n}$$
即推出 $\frac{\sum\limits_{i=1}^{n}{a_i}}{n} < \frac{\sum\limits_{i=1}^{n}{a_i}}{n}$，矛盾了。因此，$a_1 \dots a_k$ 或 $a_{k+1} \dots a_n$ 中，至少有一个部分的最大平均数子数组的平均值会大于等于整个数组 $a$ 的平均值。
由此可知，任意长度 $n \geq 4$ 的子数组都能拆分成两个长度至少为 $2$ 的子数组，其中必有一个的最大平均值不小于原数组。换句话说，每个较长的最大平均子数组都能缩短为更小的子数组而不降低均值。不断重复这一过程，最终必然得到长度为 $2$ 或 $3$ 的子数组，其平均值与初始最大值相同甚至更高。因此，只需考察所有长度为 $2$ 和 $3$ 的子数组即可。
AC 代码如下，时间复杂度为 $O(n)$：
#include <bits/stdc++.h>
using namespace std;typedef long long LL;const int N = 5e3 + 5;int a[N];int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];}LL ret = 0;for (int i = 1; i <= n; i++) {LL mx = 0;for (int j = i + 1; j <= n; j++) {mx = max(mx, ((LL)a[j] + a[j - 1]) / 2);if (j - 2 >= i) mx = max(mx, ((LL)a[j] + a[j - 1] + a[j - 2]) / 3);ret += mx;}}cout << ret;return 0;
}
日记
今天是我的生日，又是一个人很普通的过完一天，其实还不错啦。下午突然被要求写一份报告，因为想说的东西太多了，因此写了很久，最后在晚上赶完了出来（虽然并没有要求今天就要交的说）。傍晚的时候和往常一样去跑步，跑完后本来打算去面馆吃面的，结果坐满了人，没办法只能晚点再去了。不过最后还是吃上了，因为平时都是在饭堂吃，所以打算今天吃点不一样的。总的来说还不错啦，希望明年能健康快乐！生日快乐哦！
参考资料
2025年广州大学程序设计竞赛新生赛题解：https://blog.nowcoder.net/n/d49fc1f796ec4bdaad145f365d028215