我们给出了一个包含n元素的整数A数组和一个整数k。
我们需要最小化相邻元素之间的最大绝对差，以便最多可以将k元素更改为任何整数。
具有约束：所有0 <= i < n的n <= 2000和-10^9 <= A[i] <= 10^9。此外，k <= n。
我的方法是尝试二进制搜索。我将下限保持为零，将上限保持为阵列中当前相邻元素的最大绝对差。然后检查在将k个元素改变为具有相邻元素的最大绝对差之后，是否有可能使具有一定量的阵列(比如m = (l + (r - l) / 2)(成为可能。
但我无法有效地检查这种可能性？如果差异大于所述m，我试图通过改变相邻元素来强行执行。但我在这里错过了一些东西。有人能提出任何解决方案吗？
使用动态编程方法可以解决此问题。
我们将递归地将完整任务简化为子任务。对于数组中的每个位置i，如果允许我们修改k0元素，则可以构建一个数组d[i][k0]，说明数组A[0..i]和自定义k0值的子任务的答案。除了一个例外——如果A[i]没有被改变，d[i][k0]给出了这种情况的最优解。
现在，如果我们知道较小的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