专栏文章

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

DDicer_L
P12165题解参与者 3已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@mipm8xu0
此快照首次捕获于
2025/12/03 14:18
3 个月前
此快照最后确认于
2025/12/03 14:18
3 个月前
查看原文

solution

简述题意

给你 nn 个东西 11 的位置，nn 个东西 22 的位置，要求将它们一一配对，问最短总距离是多少。

思路

简单的贪心。
第 ii 个东西 11 的位置为 wiw_i，第 ii 个东西 22 的位置为 agiag_i。
先将 ww 与 agag 分别排序，再把 wiw_i 与 agiag_i 之差的绝对值加到 ansans 中，进行 nn 次。
正确性的话，错位相配对，假设 wiw_i 与 agi+1ag_{i+1} 配对，距离为 x1x_1，agiag_i 与 wi+1w_{i+1} 配对，距离为 x2x_2， 原按位配对为 x3x_3，x4x_4。如果 x3x_3 小于 x1x_1，x4x_4 小于 x2x_2，显然原来更优。如果一个更大一个更小，则相加之后和相等，结果不变。

注意点

按位配对需要排序。这道题数据小，可以放心排序。
ansans 的值偏大，需要开 longlong。Java 的同学没这个顾虑。

代码附上

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;
}
CPP
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);
    }
}

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...