题解:P12165 [蓝桥杯 2025 省 C] 最短距离

· · 题解

solution

简述题意

给你 n 个东西 1 的位置,n 个东西 2 的位置,要求将它们一一配对,问最短总距离是多少。

思路

简单的贪心。

i 个东西 1 的位置为 w_i,第 i 个东西 2 的位置为 ag_i

先将 wag 分别排序,再把 w_iag_i 之差的绝对值加到 ans 中,进行 n 次。

正确性的话,错位相配对,假设 w_iag_{i+1} 配对,距离为 x_1ag_iw_{i+1} 配对,距离为 x_2, 原按位配对为 x_3x_4。如果 x_3 小于 x_1x_4 小于 x_2,显然原来更优。如果一个更大一个更小,则相加之后和相等,结果不变。

注意点

按位配对需要排序。这道题数据小,可以放心排序。

### 代码附上 ```cpp #include <bits/stdc++.h> using namespace std; const int N=50005; #define int long long int n,w[N],ag[N],ans; signed main(){ ios::sync_with_stdio(false); cin>>n; for(int i=1;i<=n;i++) cin>>w[i]; for(int i=1;i<=n;i++) cin>>ag[i]; sort(w+1,w+1+n); sort(ag+1,ag+1+n); for(int i=1;i<=n;i++) ans+=abs(w[i]-ag[i]); cout<<ans; } ``` ``` import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] w = new int[n + 1]; int[] ag = new int[n + 1]; for (int i = 1; i <= n; i++) w[i] = sc.nextInt(); for (int i = 1; i <= n; i++) ag[i] = sc.nextInt(); Arrays.sort(w, 1, n + 1); Arrays.sort(ag, 1, n + 1); long ans = 0; for (int i = 1; i <= n; i++) { ans += Math.abs(w[i] - ag[i]); } System.out.println(ans); } } ```