最多改变k个元素使相邻元素的最大绝对差最小化

Question

我们已经获得了一个有n个元素的整数数组A和一个整数k。我们需要最小化相邻元素的最大绝对差，使得至多可以更改k个元素为任何整数。

满足约束条件：对于所有0 <= i < n，n <= 2000，-10^9 <= A[i] <= 10^9。同时，k <= n。

我的方法是尝试使用二分搜索。我将下限保持为零，将上限保持为当前数组中相邻元素的最大绝对差。 然后检查是否可能创建一个具有一定数量（假设为m = (l + (r-l) / 2)）的数组，在更改k个元素后拥有相邻元素的最大绝对差作为m。

但我无法有效地检查这种可能性？如果差异大于所述m，我试图通过更改相邻元素来强制解决问题。但我在这里失去了什么。 有人能建议任何解决方案吗？

- Pratik Sakhare

---

但是我无法检查这种可能性。为什么？ - Abhinav Mathur

实际上我的意思是暴力解决方案行不通，我想不出其他高效的解决方案。 - Pratik Sakhare

请提供足够的代码，以便他人更好地理解或重现问题。 - Community

提示：在二分搜索中，您可以使用动态规划来检查是否可以在k次更改中实现绝对差为m。 对于每个数组前缀A [0..i]和值v，编写一个动态规划公式，以获得“A [0..i]需要的更改次数，以使其绝对差最多为m，假设A [0..i]将以A [i] = v结尾”。 - kcsquared

@kcsquared：你说“鉴于A[0..i]以A[i]=v结尾”。这不是给定的。取A=[28,42,37,...]，m=10。当i=0时，不需要进行任何更改。当i=1时，A[0..1]包含一个差值为14的元素。我们可以将A[0]=42或A[1]=32..52。但是我们没有下一次迭代所需的A[1]。更糟糕的是，我们可能会同时更改A[0]和A[1]（例如A=[28,42,37,1000,1000,1000,1000]）。我认为动态规划无法解决这个问题。 - Jojonete

Answer 1

这个问题可以使用动态规划方法解决。

我们会递归地将整个任务缩小为子任务。对于数组中的每个位置，如果我们被允许修改个元素，就让我们构建一个数组，它表示A [0..i]的子任务和自定义k0值的答案是什么。有一个例外-d [i] [k0]提供了在不改变A [i]的情况下的最优解。

现在，如果我们知道更小的 i 的所有答案，就可以为d [i] [k0]构建一个答案。请记住，根据定义，A [i] 不会改变。这意味着我们可以构建一个更改值的段 A [l + 1..i-1] （这里 segment_len = i-l-1 ），再加上使用答案 d [l] [k0-segment_len] ，从这两个中，我们可以看出 d [i] [k0] 是 d [l] [k0-segment_len] 和更改段内的最小差异。我们可以看到，通过取步长等于（last-first + segment_len-1）/ segment_len ，可以最优地构建片段。

现在遍历所有段的长度，我们可以找到可能的最小 d [i] [k0] 。整个任务的最终答案是 d [n] [k] 。

我认为更好的优化是可能的，但我通过3个嵌套循环解决了这个动态规划任务。如果我给我的代码随机输入，它会在n = 1000, k = 500时在1秒钟内返回答案，在n = 2000, k = 1000时在8秒钟后返回答案。

我甚至有想法如何大大加速它。但如果我有时间的话，可能以后再实现它们。

因此，我的算法的时间复杂度是O(n * k^2)，空间复杂度是O(n * k)。 在线尝试!

#include <cstdint>
#include <vector>
#include <limits>

using i32 = int32_t;

i32 Solve(std::vector<i32> const & A, i32 n, i32 k) {
    std::vector<std::vector<i32>> d(n + 1, std::vector<i32>(k + 1));
    for (i32 i = 0; i <= n; ++i)
        for (i32 k0 = 0; k0 <= k; ++k0) {
            i32 rmin = std::numeric_limits<i32>::max();
            for (i32 j = 0; j <= k0; ++j) {
                i32 r = 0;
                if (i - 1 - j < 0)
                    r = 0;
                else if (i >= n)
                    r = d[i - 1 - j][k0 - j];
                else {
                    i32 step = (std::abs(A[i] - A[i - 1 - j]) + j) / (j + 1),
                        prev = d[i - 1 - j][k0 - j];
                    r = std::max(step, prev);
                }
                rmin = std::min(rmin, r);
            }
            d[i][k0] = rmin;
        }
    return d[n][k];
}

#include <random>
#include <chrono>
#include <iomanip>
#include <iostream>

void Test() {
    auto Time = []{
        static auto const gtb = std::chrono::high_resolution_clock::now();
        return std::chrono::duration_cast<std::chrono::duration<double>>(
            std::chrono::high_resolution_clock::now() - gtb).count();
    };

    std::mt19937_64 rng{std::random_device{}()};
    std::uniform_int_distribution<i32> distr(-1'000'000'000, 1'000'000'000);
    i32 n = 1'000, k = 500;
    std::vector<i32> A(n);
    for (size_t i = 0; i < A.size(); ++i)
        A[i] = distr(rng);
    //for (auto x: A) std::cout << x << " "; std::cout << std::endl;
    auto tim = Time();
    i32 res = Solve(A, n, k);
    tim = Time() - tim;
    std::cout << "Result " << res << ", time " << std::fixed
        << std::setprecision(4) << tim << " sec" << std::endl;
}

int main() {
    Test();
}

输出：

Result 295187479, time 1.0335 sec

- Arty