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。