题目理解

有 $n$ 个容器，第 $i$ 个容器初始有 $a_i$ 单位水。
总和 $S = \sum_{i=1}^n a_i$ 能被 $n$ 整除。
操作：选择 $i < j$，从容器 $i$ 向容器 $j$ 倒入任意数量的水（可以倒 0 单位）。
问能否通过若干次操作，使所有容器水量相等。

核心观察

1. 最终水量
   由于总水量不变，最终每个容器水量应为

   $$k = \frac{\sum_{i=1}^n a_i}{n}$$

2. 操作方向限制
   水只能从左向右倒（$i < j$）。
   这意味着：

   • 左边的水可以补给右边
   • 右边的水永远无法倒回左边

3. 从左到右贪心策略
   从左到右扫描（$i = 1 \to n-1$）：

   • 如果当前容器 $i$ 的水量 $a_i < k$，则它无法从右边得到水，直接失败
   • 如果 $a_i > k$，则多出的水必须全部倒给右边（因为不能倒回左边，也不能倒给更左边的容器）
   • 倒水后，$a_i$ 变成 $k$，$a_{i+1}$ 增加 $a_i - k$

4. 正确性说明
   由于只能向右倒，任何“缺水的容器”只能由它左边的容器补给。
   因此从左到右维护“当前容器能否达到 $k$”是充分且必要的。
   若扫描结束都没有出现缺水情况，则一定可以达成目标。

算法步骤

1. 计算总和 $sum$，得到平均值 $k = sum / n$
2. 初始化当前剩余水量为 $a_0$
3. 对 $i$ 从 $0$ 到 $n-2$：
   • 若 $a_i < k$：输出 "NO" 并结束
   • 否则，将多余的水 $a_i - k$ 加到 $a_{i+1}$ 上，并将 $a_i$ 设为 $k$
4. 若循环结束，输出 "YES"

复杂度分析

• 时间复杂度：$O(n)$ 每个测试用例
• 空间复杂度：$O(n)$ 存储数组（可优化到 $O(1)$ 但没必要）
• 总 $n$ 不超过 $2\times 10^5$，足够快

示例验证

以第三个测试用例 $[4,5,2,1,3]$ 为例：

• $sum = 15$，$n = 5$，$k = 3$
• $i = 0$：$a_0=4 > 3$，多余 $1$ 给 $a_1$ → $[3,6,2,1,3]$
• $i = 1$：$a_1=6 > 3$，多余 $3$ 给 $a_2$ → $[3,3,5,1,3]$
• $i = 2$：$a_2=5 > 3$，多余 $2$ 给 $a_3$ → $[3,3,3,3,3]$
• $i = 3$：$a_3=3 = k$，无需操作
  最终全部为 $3$，输出 "YES"

代码（已给出）

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

void solve() {
    int n;
    cin >> n;
    vector<long long> a(n);
    long long sum = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        sum += a[i];
    }
    long long k = sum / n;

    for (int i = 0; i < n - 1; i++) {
        if (a[i] < k) {
            cout << "NO" << endl;
            return;
        }
        a[i + 1] += a[i] - k;
        a[i] = k;
    }
    cout << "YES" << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

总结

本题的关键在于：

• 发现只能向右倒水的限制
• 从左到右贪心处理多余的水
• 一旦发现某容器水量不足平均值，则不可能成功

这就是 CF 1931B - Make Equal 的标准解法。