题解：P16270 [蓝桥杯 2026 省 Java B 组] 共享单车
cyz1234
·
·
题解
P16270 [蓝桥杯 2026 省 Java B 组] 共享单车 题解
题目大意
这里有 n 辆单车和 m 个停车点，问把车停完的最小花费。
题目分析
这是一个最小权匹配问题，将 n 个单车分配到 m 个停车点，使得总搬运距离最小。
不难发现，最优解中，匹配连线不会交叉。如果按位置排序后，单车 i 匹配停车点 p_i，那么排序后必有 p_1<p_2<...<p_n。
因为如果交叉，交换配对会使总距离减少或不变。
我们令 f_{i,j} 表示前 i 辆单车分配到前 j 个停车点的最小体力。那么我们可以得到动态转移方程：
那么这道题就迎刃而解了。
## 奉上代码
```cpp
#include<bits/stdc++.h>
#define int long long // 开long long
using namespace std;
const int N=5005;
int n,m,a[N],b[N],dp[N][N]; // a和b分别为单车点与停车点，dp为动态转移数组
void init(){ // 处理排序与初始化
sort(a+1,a+n+1);
sort(b+1,b+m+1); // 将两个数组从小到大排序
memset(dp,0x3f,sizeof(dp));
for(int j=0;j<=m;j++){
dp[0][j]=0;
} // 初始化动态转移数组
}
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=m;i++){
cin>>b[i];
} // 输入
init();
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
dp[i][j]=min(dp[i][j-1],dp[i-1][j-1]+abs(a[i]-b[j])); // 动态转移方程
}
}
cout<<dp[n][m]; // 输出
return 0;
}