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

victory_huyuehao · 2025-04-19 12:07:30 · 题解

新手的第一篇题解，请多多包涵！

更新： 2025 年 4 月 24 日，修改了 1 个错误，优化语言。

洛谷P12165

这是一道贪心，十分经典。

贪心思路

首先，对于输入的数据要升序排序，c++ 的 sort 函数就能解决。

通过观察，我们可以得出结论：第 i 个显示器与第 i 个插头连接时，距离最短。

但是，我们需要证明，可能会出现别的情况。

证明贪心

另一种情况：第 1 个显示器与第 n 个显示器连接，第 2 与第 n - 1 个连接……

这种情况有可能最优。

证明原来的思路很简单，举个反例。

假设 A 为显示器，B 为插头，0 为空间隔。

那么这种情况：

      A 0 B A A B 0 B
位置：0 1 2 3 4 5 6 7

按照第 1 个显示器与第 n 个显示器连接，第 2 个与第 n - 1 个连接……可以得出充电线长度：

按照第 i 个显示器与第 i 个 插头连接，则：

很显然，反例是错误的，贪心成立。

代码如下：

C++代码

#include <bits/stdc++.h>
using namespace std;
int n,a[50010],b[50010];//定义，a为显示器位置，b为插头位置
long long cnt;//计数器
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&b[i]);
    }//输入
    sort(a+1,a+n+1);
    sort(b+1,b+n+1);//排序
    for(int i=1;i<=n;i++){
        cnt+=abs(b[i]-a[i]);
    }//计数
    printf("%lld",cnt);
    return 0;
}

谢谢观看！