2 条题解
-
2
算diff(A-B或者B-A是对称的)之类,确保有效的我就不说了,本质上这个题目的diff数组可以被转化为这样的题目:
我们有一个包含正负数的数组,并且保证其平均值为0。我们的目标是通过移动正值来补偿负值,使得所有负值变为0。在这个过程中,移动一个正值的元素向左或向右一步,视为一步。请问,最小的移动步数是多少?
我们先从简单diff数组的环节开始: {a, -a} 我想这个的答案是显而易见的:。1是a和-a之间的距离。 那么稍微复杂一点的情况呢? {a, b, c},同时。
一、这里面有两个数是0。那么这是不可能的。此时不可能得出。
二、这里面有一个数是0。如果a或者c是0,那么就化归到了上面说的两个元素的情况,而且必然互为相反数。如果b是0,那么其实也是化归到了两个元素的情况,不过此时距离是2,这个值得注意。而且你会发现,他们的计算方式是可以被统一的。
三、他们都不是0。那么此时的正负分布有八种情况。而其中,为了满足,他们不可能是全正全负。而剩下的六种情况中,又存在对称性: {-, -, +}和{+, +, -}对称 {-, +, -}和{+, -, +}对称 {+, -, -}和{-, +, +}对称 也就是说实际上我们只需要研究三种情况就已经足够了。我们选择一正二负的情况来深入探讨。
首先是{a, b, c}对应的{-, -, +}情况。这种情况下,想要找到最短路径,其实就是让c这个正数往左边去填充。结果是。我们还可以这么解释这个结果:a从b那里借来了abs(a)个糖果,这个时候就是{0, b - abs(a), c},但是要注意,这个糖果迁移的距离是要被计算的,也就是。注意,这个时候b和a都是负数,因此实际上b - abs(a)是需要个糖果。这个时候就化归为了之前说的两个元素情况。此时的路径为。那再结合一下之前之前的路径,其实就是。
剩下的两种情况也差不多。这个可以当作课后习题,主要是因为我懒得打了。总而言之你会发现剩下的三种使用这种“借过来”的思维之后,是可以统一运算的人。代码如下:
#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; }
信息
- ID
- 12
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 3
- 标签
- 递交数
- 10
- 已通过
- 7
- 上传者