思路

题目要求最终的 a 数组中每个数都必须在 b 中出现过，且 a 数组最终是一个单调不降的数组，所以可以考虑确定 a 数组中最大的值，即第 n 个数的最终值。

状态定义 考虑 dp[i][j] 表示 a 的第 i 个数为 j ，前 i 个数是单调不降的最小操作次数。 状态转移

• 第 i-1 个数为 j：dp[i][j] = dp[i - 1][j] + abs(a[i]-j)
• 第 i-1 个数为 j-1 ：dp[i][j] = dp[i - 1][j - 2] + abs(a[i]-j)
• 第 i-1 个数为 j-2 ：dp[i][j] = dp[i - 1][j - 1] + abs(a[i]-j)
• ...
• 第 i-1 个数为 1 ：dp[i][j] = dp[i - 1][1] + abs(a[i]-j) 最终答案就是 min(dp[n][1:])

但是这里还需要有一个限定条件，即每个数都得在 b 中出现过。 那么可以将 b 进行一个排序， 改变一下状态定义：dp[i][j] 表示 a 的第 i 个数为 b[j] ，前 i 个数均在 b 中出现过，且单调不降的最小操作次数。 状态转移

• 第 i-1 个数为 b[j]：dp[i][j] = dp[i - 1][j] + abs(a[i]-b[j])
• 第 i-1 个数为 b[j-1] ：dp[i][j] = dp[i - 1][j - 1] + abs(a[i]-(b[j]))
• 第 i-1 个数为 b[j-2] ：dp[i][j] = dp[i - 1][j - 2] + abs(a[i]-(b[j]))
• ...
• 第 i-1 个数为 b[1] ：dp[i][j] = dp[i - 1][1] + abs(a[i]-b[j]) 最终答案仍为 max(dp[n][1:])

但是这样的状态枚举是 $O(nm)$ ，状态转移是 $O(m)$ 的，总时间复杂度为 $O(nm^2)$ ，无法通过本题。

考虑如何优化，可以发现 dp[i][j] = min(dp[i-1][1:j+1]) + abs(a[i]-b[j])

所以我们可以动态维护一个 dp[i-1] 的最小值，这样就可以优化为 $O(nm)$ 了。

时间复杂度：$O(nm)$

代码

C++

#include<bits/stdc++.h>
using namespace std;
const int N=2e3+10;
long long a[N],b[N],n,m;
long long f[N][N];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=m;i++)cin>>b[i];
    sort(b+1,b+1+m);
    memset(f,0x3f,sizeof f);
    for(int j=0;j<=m;j++)f[0][j]=0;
    for(int i=1;i<=n;i++){
        vector<long long>pre(m+1,1e18);   //维护前缀和的最小值
        pre[0]=f[i-1][0];
        for(int j=1;j<=m;j++){
            pre[j]=min(pre[j-1],f[i-1][j]);
        }
        for(int j=1;j<=m;j++){
            f[i][j] = pre[j]+ abs(a[i]-b[j]);
        }
    }
    long long res=1e18;
    for(int i=1;i<=m;i++)res=min(res,f[n][i]);
    cout<<res<<endl;
    return 0;
}

INF = 10 ** 18

n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

b.sort()

dp = [[INF for _ in range(m + 1)] for _ in range(n + 1)]
dp[0][:] = [0] * (m + 1)

for i in range(1, n + 1):
    prefix_min = INF
    for j in range(1, m + 1):
        val = abs(a[i - 1] - b[j - 1])
        prefix_min = min(prefix_min, dp[i - 1][j])
        dp[i][j] = prefix_min + val


print(min(dp[n][1:]))

小苯有一个长度为$n$的数组 a，小红有一个长度为$m$的数组 b 小苯希望对$a$中的元素进行一些变换，使得$a$的所有元素都在$b$中出现过。具体的，他可以做任意如下操作:

• 选择$i(1\le i\le n)$，令$a_i=a_i+1$或$a_i=a_i-1$.

小苯想在变换后，同时又能使得a单调不降，他想知道他最少需要操作多少次，请你帮帮他吧。

输入描述

输入包含三行。第一行两个正整数$n,m(1\le n,m\le 2\times 10^3)$，分别表示$a$和$b$的长度。 第二行$n$个正整数$a_i(1\le a_i\le 10^9)$，表示$a$数组初始时所有的元素。

第三行$m$个正整数$b_i(1\le b_i\le 10^9)$，表示$b$数组的所有元素。

输出描述

输出一个整数，表示最少操作次数

样例1

输入

5 4
3 5 3 8 10
1 2 3 4

输出

12

样例2

输入

5 3
1 2 3 3 3 
1 2 3

输出

0