显示器插座最短连线算法(蓝桥杯十六届C组编程题第二题)

样例输入：

2

0

1

2

3

样例输出：

4

代码如下：

#include <stdio.h>

long long calcuateMinLength(int xianshiqi[],int chazuo[],int n)
{
int i,j,temp;

for(int i=0;i < n - 1;i++){
for(int j=0;j < n-1-i;j++){
if(xianshiqi[j] > xianshiqi[j+1]){
temp = xianshiqi[j];
xianshiqi[j] = xianshiqi[j + 1];
xianshiqi[j + 1] = temp;
}
}
}

for(int i=0;i < n-1;i++){
for(int j=0;j< n-1-i;j++){
if(chazuo[j] > chazuo[j+1]){
temp = chazuo[j];
chazuo[j] = chazuo[j + 1];
chazuo[j + 1] = temp;
}
}
}

long long totalLength = 0;

for(int i=0;i< n ;i++){
int cha = chazuo[i] - xianshiqi[i];
if(cha < 0){
cha = -cha;
}
totalLength += cha;
}

return totalLength;

}
int main()
{
int n;
int dq[50005];
int cz[50005];
int k;

scanf("%d",&n);

for(k=0;k<n;k++){
scanf("%d",&dq[k]);
}

for(k=0;k<n;k++){
scanf("%d",&cz[k]);
}
printf("%lld",calcuateMinLength(dq,cz,n));

return 0;
}

🧠 核心函数：calcuateMinLength

第一步：给显示器排队（冒泡排序）

• 目的：把所有显示器按照坐标从小到大排列。

• 原理：就像排队一样，相邻的两个人比大小。如果左边的人（xianshiqi[j]）比右边的人（xianshiqi[j+1]）大（也就是坐标更靠右），就让他们交换位置。

• 结果：这一通折腾下来，xianshiqi数组里，坐标小的在最前面，坐标大的在最后面。

第二步：给插座排队（冒泡排序）

• 目的：同理，把所有插座也按照坐标从小到大排列。

第三步：一一对应连线（贪心策略）

• 核心逻辑：
  • 现在显示器排好队了，插座也排好队了。
  • 我们让第 1 个显示器连第 1 个插座，第 2 个显示器连第 2 个插座……以此类推。
  • 这就是所谓的“贪心算法”：排序后一一对应，总距离最短。
• 计算距离：
  • chazuo[i] - xianshiqi[i]：算出两个坐标的差。
  • if(cha < 0) cha = -cha;：这一步是在求绝对值。因为线长不能是负数，比如插座在左边（坐标小），显示器在右边（坐标大），减出来是负数，我们要把它变成正数。
• 累加：把每一根线的长度都加到totalLength里。

注意：这里用了long long来存总长度。因为题目里说坐标最大是 109109 ，如果有 5 万个这样的数加起来，普通的int存不下（会溢出爆炸），必须用更大的long long。

🏭 主函数：main

主函数负责“招兵买马”和“发号施令”。

1. 定义大数组：int dq[50005];和int cz[50005];。题目说最多50000个设备，这里开稍微大一点点，防止不够用。
2. 输入数据：
   • 先读n。
   • 第一个for循环：把显示器的坐标一个个读进dq数组。
   • 第二个for循环：把插座的坐标一个个读进cz数组。
3. 调用计算：printf("%lld", calcuateMinLength(dq, cz, n));
   • 把装好数据的数组扔进刚才写的函数里。
   • 拿到返回的结果，用%lld格式打印出来。

📌 总结

这段代码虽然用的是最基础的冒泡排序（效率略低，但在 �=50000N=50000 时可能会稍微慢一点点，不过逻辑完全正确），但它的优点在于可读性极强。它完美地展示了“排序 + 贪心”的解题思路：

1. 把乱的坐标理整齐（排序）。
2. 按顺序一个个配对（贪心）。
3. 算出距离加起来（累加）