C++ 经典算法问题：管道问题 丨排序算法练习

问题说明

某石油公司计划建造一条由东向西的主输油管道。 该管道要穿过一个有n 口油井的油田。 从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。 如果给定n口油井的位置,即它们的x 坐标（东西向）和y 坐标（南北向）, 应如何确定主管道的最优位置, 即使各油井到主管道之间的输油管道长度总和最小的位置?

功能说明

本程序用排序求中值的方法求解输油管道问题。

代码简述

通过用户输入数据（只输入油井数n、每个油井的y坐标）， 程序输入检测，动态分配空间，排序（使用快速排序）， 求出中间值，输出。

输出有以下两种情况：

（1）当n为奇数，则最优位置为y数组的第n/2个油井的y坐标

（2）当n为偶数，则最优位置为y数组的中间两个油井的y坐标的区间

代码示例

#include<iostream>usingnamespacestd;//油井y坐标指针float* y =NULL;//快速排序voidquick_sort(intlow,inthigh){if(low >= high)//结束标志return;intfirst = low;//低位下标intlast = high;//高位下标floatkey = y[first];//设第一个为基准while(first < last){//将比第一个小的移到前面while(first < last && y[last] >= key)last--;if(first < last)y[first++] = y[last];//将比第一个大的移到后面while(first < last && y[first] <= key)first++;if(first < last)y[last--] = y[first];}//基准置位y[first] = key;//前半递归quick_sort(low, first -1);//后半递归quick_sort(first +1, high);}intmain(){intn;//油井数floatmid;//y数组的中间位置的数floatminDistance =0;//各油井到主管道之间的管道长度总和最小位置cout <<"---------------- 输油管问题 ----------------"<< endl;cout <<"请输入油井数 n (n>=0)"<< endl;//输入油井数cin >> n;//判断输入数据合法性，包括检查输入是否为数字，k值是否大于0if(cin.fail() || n <0){cout <<"输入n错误！"<< endl;system("pause");return0;}//分配n个y坐标存储空间y =newfloat[n];cout <<"请输入"<< n <<"个油井的 y 坐标（用空格隔开）"<< endl;//输入油井的 y 坐标for(autoi =0; i < n; i++){cin >> y[i];}//判断输入数据合法性if(cin.fail()){cout <<"输入y坐标错误！"<< endl;system("pause");return0;}//运用快速排序对y坐标数组进行排序quick_sort(0, n -1);//计算y数组的中间位置的数mid = y[n /2];//计算各个油井到主输油管的长度之和for(autoi =0; i < n; i++){minDistance +=abs(y[i] - mid);}//显示输出cout <<"------------------------------------------------"<< endl;//判断油井奇偶，做不同的输出if(n &1){//n为奇数，则最优位置为y数组的第n/2个油井的y坐标cout <<"主管道的最优位置为：y ="<< mid << endl;}else{//n为偶数，则最优位置为y数组的中间两个油井的y坐标的区间cout <<"主管道的最优位置为：y = ["<< y[n /2-1] <<","<< mid <<"]"<< endl;}//输出各油井到主管道之间的管道总长度cout <<"各油井到主管道之间的管道总长度为："<< minDistance << endl;cout <<"------------------------------------------------"<< endl;//暂停查看结果system("pause");//释放内存delete[]y;//指针置空y =NULL;return0;}

今天的分享就到这里了，大家要好好学C++哟~

写在最后：对于准备学习C/C++编程的小伙伴，如果你想更好的提升你的编程核心能力（内功）不妨从现在开始！

微信公众号：C语言编程学习基地

整理分享（多年学习的源码、项目实战视频、项目笔记，基础入门教程）

欢迎转行和学习编程的伙伴，利用更多的资料学习成长比自己琢磨更快哦！