题解 | #操作数组#

1. 问题分析

该问题的本质是一个带有守恒约束的线性变换问题。

操作特性：每次操作选择两个不同的索引 $i, j$ ，使 $a_i$ 减 1，同时 $a_j$ 加 1。这一操作在数学上等价于在数组元素之间进行“单位增量的转移”。
和的不变性（Invariant）：无论执行多少次操作，数组 $a$ 的元素总和 $\sum a_i$ 始终保持不变。
目标状态：通过最少次数的单位转移，使得对于所有 $1 \le i \le n$ ，都有 $a_i = b_i$ 。

2. 算法：不变量与偏差抵消

基于上述分析，我们可以推导出：

判定必要条件（可达性分析）：要使 $a$ 能够转化为 $b$ ，最基本的物理前提是两者的总和必须相等。若 $\sum a_i \neq \sum b_i$ ，则无论执行多少次操作，均无法达成目标，直接返回 -1。
贪心与偏差计算：定义 $d_i = a_i - b_i$ 为位置 $i$ 处的偏差量：
- 若 $d_i > 0$ ，说明该位置存在“盈余”，需要移出 $d_i$ 个单位。
- 若 $d_i < 0$ ，说明该位置存在“亏空”，需要移入 $|d_i|$ 个单位。
由于每次操作固定将 1 个单位从某处移至另一处，每一次操作最多能同时抵消 1 个单位的盈余和 1 个单位的亏空。
最优性证明：最小操作次数等于总盈余量（或总亏空量的绝对值）。

设 $S_{plus} = \sum_{d_i > 0} d_i$ ，设 $S_{minus} = \sum_{d_j < 0} |d_j|$ 。

当满足 $\sum a_i = \sum b_i$ 时，必然有 $S_{plus} = S_{minus}$ 。

由于一次操作能让 $S_{plus}$ 减少 1 且让 $S_{minus}$ 减少 1，因此达到目标状态（即 $S_{plus} = S_{minus} = 0$ ）所需的最少步数即为 $S_{plus}$ 。

3. 复杂度分析

时间复杂度： $O(n)$ 。算法仅需遍历数组两次：一次用于求和校验，一次用于计算偏差。
空间复杂度： $O(1)$ 。除了存储输入数组外，仅需常数级别的变量用于计数，具有极高的空间利用率。

4. 代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

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

    int n;
    cin >> n;
    vector<ll> a(n), b(n);
    ll S1 = 0;
    ll S2 = 0;

    for (int i = 0; i < n; i++) {
        cin >> a[i];
        S1 += a[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
        S2 += b[i];
    }
    if (S1 != S2) {
        cout << -1 << endl;
        return 0;
    }

    ll ops = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] > b[i]) {
            ops += a[i] - b[i];
        }
    }
    cout << ops << endl;
}