使序列的所有元素都为 0 所需的最少步数

Question

给定一个整数序列，计算使所有数字为 0 所需的最少操作次数。操作如下：从索引 i 到索引 j 的所有数字增加或减少 1。

示例 1)

{1, 1, -1}

你可以做到：

将索引从 0 减少到 1

将索引增加 2 到 2

所以答案是2次操作。

示例 2)

{3, -1, -1, 3}

减少索引 0 到 3

增加索引 1 到 2

所以答案是 7。

执行此操作的有效算法是什么？

Answer 1

一个问题是有很多方法可以使最终结果为 0，即使在所有情况下操作次数最少也是如此。

例如，对于 {1, 0, 1}，我们在 [0, 2] 上应用 -1，在 [1, 1]
上应用 +1 或者我们可以在 [0, 0] 上应用 -1，然后在 [2, 2].

上应用 -1

在这两种情况下，都需要进行两次操作。

由于只需要最少数量的操作，我们可以决定在看起来不是最理想的情况下尽快将操作拆分为不同的间隔。

然后，通过比较相邻索引之间的值来应用迭代过程。

例如，如果符号不同，或者新值是0，我们可以决定拆分区间。

#include <iostream>
#include <vector>

int count_operations (const std::vector<int> &A) {
    int n = A.size();
    if (n == 0) return 0;
    int count = std::abs (A[0]);
    for (int i = 1; i < n; ++i) {
        if (A[i]*A[i-1] > 0) {
            if(std::abs(A[i]) > std::abs(A[i-1])) {
                count += std::abs(A[i]) - std::abs(A[i-1]);
            }
        } else {
            count += std::abs(A[i]);
        }
    }
    return count;
}

int main() {
    std::vector<int> A = {1 , 1, -1};
    auto ans = count_operations (A);
    std::cout << ans << "\n";
    
    A = {3, -1, -1, 3};
    ans = count_operations (A);
    std::cout << ans << "\n";
    
    return 0;
}

使序列的所有元素都为 0 所需的最少步数

Minimum number of steps required to make all elements of sequence 0

algorithm

greedy