2 条题解

  • 2
    @ 2024-8-16 20:28:48

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

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

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

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

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

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

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

      哇,写的是真好

    • @ 2024-8-17 16:01:51

      @ 老师竟然会夸人⭐v⭐

    • @ 2024-8-18 1:51:05

      @其实我还是感觉我写的不是太好。我这里想说的更为主要的思想是化归。先从最简单的情况开始,然后逐步复杂。但我在这里其实没有体现出如何从3化归为2,而只是对3做了穷举。我一开始的想法是3作为基底,剩下的情况都可以划归为3,但我好像忘了写了(

      含有三个元素的情况是可以化归位含有两个元素的情况的,这个是无后效性的。如果看不懂我这里在说什么可以问一下罐头老师,毕竟我只是一个路过的热心网友。我就不推荐你们用GPT之类的大语言模型了,因为真的很容易痴迷上,然后就丢失了自己独立做题的能力。

    • @ 2024-8-18 1:57:17

      @关于证明当前最优解是全局最优解的方法,我觉得可以用一下反证法——比如说假设我现在的做法并不好,随后我们找另外一个做法,然后大概会发现另一个做法并不是最好的做法,由此证明了我现在的方法是最好的方法。同时,a,b,c也不一定非得代表一个数,也可以说是某一段(这个段包括只含有一个数的情况,这很关键)的最优解。

      这个时候我们又面临另一个问题了,当我们这么想的时候,a或b或c代表的某段的和不一定是0,此时如何决定它的最优解呢?我猜测是让非0值出现在左边或者右边,而这应该是对称的,也就是说我只需要保证非0值出现在边界就可以了。这只是一个大概的思路,很难说这算不算是一个题解。我觉得这个题目还有地方可以挖,以及很多的变种

信息

ID
12
时间
1000ms
内存
256MiB
难度
3
标签
递交数
10
已通过
7
上传者