算diff（A-B或者B-A是对称的）之类，确保有效的我就不说了，本质上这个题目的diff数组可以被转化为这样的题目：

我们有一个包含正负数的数组，并且保证其平均值为0。我们的目标是通过移动正值来补偿负值，使得所有负值变为0。在这个过程中，移动一个正值的元素向左或向右一步，视为一步。请问，最小的移动步数是多少？

我们先从简单diff数组的环节开始： {a, -a} 我想这个的答案是显而易见的：$ans = a \times 1$。1是a和-a之间的距离。 那么稍微复杂一点的情况呢？ {a, b, c}，同时$a + b + c = 0$。

一、这里面有两个数是0。那么这是不可能的。此时不可能得出$a + b + c = 0$。

二、这里面有一个数是0。如果a或者c是0，那么就化归到了上面说的两个元素的情况，而且必然互为相反数。如果b是0，那么其实也是化归到了两个元素的情况，不过此时距离是2，这个值得注意。而且你会发现，他们的计算方式是可以被统一的。

三、他们都不是0。那么此时的正负分布有八种情况。而其中，为了满足$a + b + c = 0$，他们不可能是全正全负。而剩下的六种情况中，又存在对称性： {-, -, +}和{+, +, -}对称 {-, +, -}和{+, -, +}对称 {+, -, -}和{-, +, +}对称 也就是说实际上我们只需要研究三种情况就已经足够了。我们选择一正二负的情况来深入探讨。

首先是{a, b, c}对应的{-, -, +}情况。这种情况下，想要找到最短路径，其实就是让c这个正数往左边去填充。结果是$a * 2 + b$。我们还可以这么解释这个结果：a从b那里借来了abs(a)个糖果，这个时候就是{0, b - abs(a), c}，但是要注意，这个糖果迁移的距离是要被计算的，也就是$a * 1$。注意，这个时候b和a都是负数，因此实际上b - abs(a)是需要$a + b$个糖果。这个时候就化归为了之前说的两个元素情况。此时的路径为$(a + b) * 1$。那再结合一下之前之前的路径，其实就是$a * 2 + b$。

剩下的两种情况也差不多。这个可以当作课后习题，主要是因为我懒得打了。总而言之你会发现剩下的三种使用这种“借过来”的思维之后，是可以统一运算的人。代码如下：

#include <iostream>
#include <vector>
#include <cmath>
#include <numeric>  // 包含 accumulate 函数

using namespace std;

int move(vector<int>& diff) {
    int count = 0;
    int n = diff.size();

    for (int i = 0; i < n; ++i) {
        if (diff[i] != 0) {
            count += abs(diff[i]);  // 累加当前差值的绝对值
            if (i + 1 < n) {  // 确保不会越界
                diff[i + 1] += diff[i];  // 将当前差值转移到下一个元素
            }
            diff[i] = 0;  // 当前元素的差值归零
        }
    }
    return count;
}

int main() {
    int n;
    cin >> n;  // 输入数组长度
    vector<int> A(n), B(n);

    // 输入数组 A
    for (int i = 0; i < n; ++i) {
        cin >> A[i];
    }

    // 输入数组 B
    for (int i = 0; i < n; ++i) {
        cin >> B[i];
    }

    // 计算差值数组
    vector<int> diff(n);
    for (int i = 0; i < n; ++i) {
        diff[i] = A[i] - B[i];
    }

    // 检查差值数组的总和
    if (accumulate(diff.begin(), diff.end(), 0) < 0) {
        cout << -1 << endl;  // 如果总和小于0，输出-1
    } else {
        cout << move(diff) << endl;  // 否则调用 move 函数并输出结果
    }

    return 0;
}

c++罐头的糖题解

没想到啊，咱们陈老师还做起oj了

问题分析

题目要求我们将一堆糖果从初始状态 A 变换到目标状态 B，每次操作可以将一颗糖果从一个堆移动到相邻的堆。我们需要计算最少需要多少步才能完成这个变换。

关键点

1. 总糖果数相同：首先需要判断两个状态的总糖果数是否相同。如果不同，则无法通过移动糖果的方式将 A 变成 B，直接输出 -1。
2. 差值计算：计算每个位置上 A 和 B 的差值。
3. 移动策略：根据差值的大小和方向，决定糖果的移动方向和步数。

解题思路

1. 输入处理：读取输入的 n 和两个数组 a 和 b。
2. 总糖果数检查：计算 a 和 b 的总糖果数，如果不相同，输出 -1。
3. 差值计算：计算每个位置上 a[i] 和 b[i] 的差值 s。
4. 移动计算：
   • 如果 s > 0，表示 a[i] 比 b[i] 多，需要将多余的糖果移动到后面的堆。
   • 如果 s < 0，表示 a[i] 比 b[i] 少，需要从后面的堆移动糖果到 a[i]。

代码实现

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin>>n;
	vector<int>a(n),b(n);
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	for(int i=0;i<n;i++){
		cin>>b[i];
	}
	int sum1=0,sum2=0;
	for(int i=0;i<n;i++){
		sum1+=a[i];
		sum2+=b[i];
	}
	if(sum1!=sum2){
		cout<<-1<<endl;
		return 0;
	}
	long long ans=0;
	for(int i=0;i<n;i++){
		int s=a[i]-b[i];
		if(s>0){
			for(int j=i+1;j<n;j++){
				if(s>0&&b[j]>a[j]){
					int t=min(s,b[j]-a[j]);
					ans+=t*(j-i);
					s-=t;
					a[j]+=t;
				}
			}
		}else if(s<0){
			for(int j=i+1;j<n;j++){
				if(s<0&&a[j]>b[j]){
					int t=min(-s,a[j]-b[j]);
					ans+=t*(j-i);
					s+=t;
					a[j]-=t;
				}
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}

复杂度分析

• 时间复杂度：O(n^2)，在最坏情况下，每个位置都需要遍历后面的所有位置来计算移动步数。
• 空间复杂度：O(n)，用于存储输入的数组 a 和 b。