调整数组使相邻元素差≤D的最小移动代价算法求解

问题描述 #

给定长度为N的整数数组A，你可以任意增大或减小数组元素的值，要求调整后的数组S满足对于所有0 < i < N，都有|S[i] - S[i - 1]| <= D，且调整的总移动代价最小（移动代价为所有元素增减量的绝对值之和），最终输出这个最小总代价。

示例说明 #

• 示例1：数组参数为N = 7, D = 3，原数组为[2, 10, 2, 6, 4, 3, 3]。调整规则为不修改第一个元素，第二个元素从10下调到5（因为A[0] + 3 = 5），第三个元素不变，第四个元素从6下调到5（因为A[2] + 3 = 5），剩余元素相邻差均不超过D无需调整。总代价为6：10→5增量绝对值为5，6→5增量绝对值为1，总和为6。
• 示例2：数组参数为N =7, D=0，原数组为[1,4,1,2,4,2,2]。因为D=0，所有元素需调整为相同值。最优方案从末尾元素开始调整：A[6]、A[5]保持为2不变，A[4]从4下调到2（代价+2），A[3]从1上调到2（代价+1），A[1]从4下调到2（代价+2），A[0]从1上调到2（代价+1），总代价为6。
• 其他测试用例：
  1. N = 7, D = 1 [2, 10, 0, 2, 4, 3, 3] 正确输出：10
  2. N = 5, D = 1 [6, 5, 4, 3, 2] 正确输出：0

现有代码问题分析 #

你目前的代码核心逻辑是分别从左到右、从右到左做单次调整，取两者最小代价，这个思路存在本质缺陷：

1. 单次单向扫描只会固定当前位置的取值，没有考虑后续元素的约束会反过来影响前面已经确定的值，无法得到全局最优解。
2. 步长计数的代价计算方式效率极低，且只处理了相邻差超标的情况，完全没有考虑总代价最小的核心要求。

正确算法思路 #

这是典型的动态规划优化类问题：

1. 先做两次双向扫描确定每个位置的合法取值上下界：
   • 从左到右扫描：low[i] = max(low[i], low[i-1] - D)，high[i] = min(high[i], high[i-1] + D)，初始low[0] = high[0] = A[0]
   • 再从右到左扫描修正边界：low[i] = max(low[i], low[i+1] - D)，high[i] = min(high[i], high[i+1] + D)
2. 基于合法区间做动态规划，用滑动窗口最小值优化转移复杂度：
   • 定义dp[i][v]为处理到第i个元素、取值为v时的最小总代价
   • 转移方程：dp[i][v] = |v - A[i]| + min(dp[i-1][u] | u ∈ [v-D, v+D])
   • 用前缀最小值数组优化min的计算，可将转移复杂度降到线性。

参考实现代码 #

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll INF = 1e18;

int main() {
    int n, d;
    cin >> n >> d;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    
    vector<int> low(n), high(n);
    int offset = 2000; // 可根据实际值域调整，也可做离散化优化
    low[0] = high[0] = a[0];
    for (int i = 1; i < n; i++) {
        low[i] = a[i] - offset;
        high[i] = a[i] + offset;
        low[i] = max(low[i], low[i-1] - d);
        high[i] = min(high[i], high[i-1] + d);
    }
    for (int i = n-2; i >= 0; i--) {
        low[i] = max(low[i], low[i+1] - d);
        high[i] = min(high[i], high[i+1] + d);
    }
    
    vector<ll> prev_dp(2*offset + 1, INF);
    for (int v = low[0]; v <= high[0]; v++) {
        prev_dp[v - a[0] + offset] = abs(v - a[0]);
    }
    
    for (int i = 1; i < n; i++) {
        vector<ll> curr_dp(2*offset + 1, INF);
        vector<ll> pre_min(2*offset + 1);
        pre_min[0] = prev_dp[0];
        for (int k = 1; k <= 2*offset; k++) {
            pre_min[k] = min(pre_min[k-1], prev_dp[k]);
        }
        for (int v = low[i]; v <= high[i]; v++) {
            int idx = v - a[i] + offset;
            int l = max(0, (v - d) - a[i-1] + offset);
            int r = min(2*offset, (v + d) - a[i-1] + offset);
            if (l > r) continue;
            ll min_prev = pre_min[r];
            if (l > 0) min_prev = min(min_prev, pre_min[l-1]);
            if (min_prev == INF) continue;
            curr_dp[idx] = abs(v - a[i]) + min_prev;
        }
        prev_dp = move(curr_dp);
    }
    
    ll ans = INF;
    for (int v = low[n-1]; v <= high[n-1]; v++) {
        ans = min(ans, prev_dp[v - a[n-1] + offset]);
    }
    cout << ans << endl;
    return 0;
}

内容的提问来源于stack exchange，提问作者Perpetual Desire