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

样例输入20123样例输出4代码如下#include stdio.hlong long calcuateMinLength(int xianshiqi[],int chazuo[],int n){int i,j,temp;for(int i0;i n - 1;i){for(int j0;j n-1-i;j){if(xianshiqi[j] xianshiqi[j1]){temp xianshiqi[j];xianshiqi[j] xianshiqi[j 1];xianshiqi[j 1] temp;}}}for(int i0;i n-1;i){for(int j0;j n-1-i;j){if(chazuo[j] chazuo[j1]){temp chazuo[j];chazuo[j] chazuo[j 1];chazuo[j 1] temp;}}}long long totalLength 0;for(int i0;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(k0;kn;k){scanf(%d,dq[k]);}for(k0;kn;k){scanf(%d,cz[k]);}printf(%lld,calcuateMinLength(dq,cz,n));return 0;}代码中的变量含义备注xianshiqi[]显示器数组存放所有显示器的坐标位置chazuo[]插座数组存放所有插座的坐标位置n数量显示器和插座各有多少个totalLength总长度最终答案所有线的长度之和cha差值两个坐标之间的距离 核心函数calcuateMinLength第一步给显示器排队冒泡排序目的把所有显示器按照坐标从小到大排列。原理就像排队一样相邻的两个人比大小。如果左边的人xianshiqi[j]比右边的人xianshiqi[j1]大也就是坐标更靠右就让他们交换位置。结果这一通折腾下来xianshiqi数组里坐标小的在最前面坐标大的在最后面。第二步给插座排队冒泡排序目的同理把所有插座也按照坐标从小到大排列。第三步一一对应连线贪心策略核心逻辑现在显示器排好队了插座也排好队了。我们让第 1 个显示器连第 1 个插座第 2 个显示器连第 2 个插座……以此类推。这就是所谓的“贪心算法”排序后一一对应总距离最短。计算距离chazuo[i] - xianshiqi[i]算出两个坐标的差。if(cha 0) cha -cha;这一步是在求绝对值。因为线长不能是负数比如插座在左边坐标小显示器在右边坐标大减出来是负数我们要把它变成正数。累加把每一根线的长度都加到totalLength里。注意这里用了long long来存总长度。因为题目里说坐标最大是 109109 如果有 5 万个这样的数加起来普通的int存不下会溢出爆炸必须用更大的long long。 主函数main主函数负责“招兵买马”和“发号施令”。定义大数组int dq[50005];和int cz[50005];。题目说最多50000个设备这里开稍微大一点点防止不够用。输入数据先读n。第一个for循环把显示器的坐标一个个读进dq数组。第二个for循环把插座的坐标一个个读进cz数组。调用计算printf(%lld, calcuateMinLength(dq, cz, n));把装好数据的数组扔进刚才写的函数里。拿到返回的结果用%lld格式打印出来。 总结这段代码虽然用的是最基础的冒泡排序效率略低但在 50000N50000 时可能会稍微慢一点点不过逻辑完全正确但它的优点在于可读性极强。它完美地展示了“排序 贪心”的解题思路把乱的坐标理整齐排序。按顺序一个个配对贪心。算出距离加起来累加