文件名称:3
介绍说明--下载内容均来自于网络,请自行研究使用
根据题目可分析:假设主管道位于所有管道的东侧(或是西侧),则测得个油井到主管道之间的输油管道总长度为sum1,若主管道的位置位于所有管道纵坐标的中位值,其输油管道总长度为sum2。由此可推算出sum1>=sum2。因此我采用第二个思路,进而将问题转化为求n个数中第k大数是什么的问题。
总的输油管道长度可通过每个输油管道的纵坐标减中位值得到,最后即可解决问题。
根据题目要求,需在线性时间内确定主管道的最优位置。在排序算法中,最优的便是快速排序,而根据题目要求,我们又不需要将所有n个数进行排序,因此可以采用快速排序的思想,达到目的。(According to the subject analysis, it is assumed that the chief pipeline is located on the east side of all pipes (or the west side), the total length of the oil pipeline between the oil well and the main pipe is sum1. If the position of the main pipe is located in the middle of all the longitudinal coordinates of the pipe, the total length of the pipeline is sum2. Thus, sum1>=sum2 can be calculated. So I use second ideas to transform the problem into the problem of finding K number in N numbers.
The length of the total oil pipeline can be obtained by reducing the median value of each oil pipeline, and finally, it can solve the problem.
According to the requirements of the subject, we need to determine the optimal location of the main pipeline in a linear time. In the sorting algorithm, the best is the fast sorting, and according to the title, we do not need to sort all the N numbers, so we can use the idea of fast sorting to achieve the goal.)
总的输油管道长度可通过每个输油管道的纵坐标减中位值得到,最后即可解决问题。
根据题目要求,需在线性时间内确定主管道的最优位置。在排序算法中,最优的便是快速排序,而根据题目要求,我们又不需要将所有n个数进行排序,因此可以采用快速排序的思想,达到目的。(According to the subject analysis, it is assumed that the chief pipeline is located on the east side of all pipes (or the west side), the total length of the oil pipeline between the oil well and the main pipe is sum1. If the position of the main pipe is located in the middle of all the longitudinal coordinates of the pipe, the total length of the pipeline is sum2. Thus, sum1>=sum2 can be calculated. So I use second ideas to transform the problem into the problem of finding K number in N numbers.
The length of the total oil pipeline can be obtained by reducing the median value of each oil pipeline, and finally, it can solve the problem.
According to the requirements of the subject, we need to determine the optimal location of the main pipeline in a linear time. In the sorting algorithm, the best is the fast sorting, and according to the title, we do not need to sort all the N numbers, so we can use the idea of fast sorting to achieve the goal.)
相关搜索: 算法
(系统自动生成,下载前可以参看下载内容)
下载文件列表
文件名 | 大小 | 更新时间 |
---|---|---|
3 | 0 | 2016-10-31 |
3\3.dsp | 4225 | 2016-10-28 |
3\3.dsw | 510 | 2016-10-28 |
3\3.ncb | 41984 | 2016-10-31 |
3\3.opt | 48640 | 2016-10-31 |
3\3.plg | 1277 | 2016-10-30 |
3\Debug | 0 | 2016-10-30 |
3\Debug\3.exe | 184394 | 2016-10-30 |
3\Debug\3.ilk | 211552 | 2016-10-30 |
3\Debug\3.pch | 204204 | 2016-10-30 |
3\Debug\3.pdb | 1082368 | 2016-10-30 |
3\Debug\pipeline.obj | 8098 | 2016-10-30 |
3\Debug\vc60.idb | 74752 | 2016-10-30 |
3\Debug\vc60.pdb | 110592 | 2016-10-30 |
3\pipeline.cpp | 2688 | 2016-10-30 |
3\test | 0 | 2016-10-30 |
3\test\Debug | 0 | 2016-10-30 |
3\test\Debug\test.exe | 184402 | 2016-10-30 |
3\test\Debug\test.ilk | 198144 | 2016-10-30 |
3\test\Debug\test.pch | 220912 | 2016-10-30 |
3\test\Debug\test.pdb | 451584 | 2016-10-30 |
3\test\Debug\test1.obj | 6568 | 2016-10-30 |
3\test\Debug\vc60.idb | 33792 | 2016-10-30 |
3\test\Debug\vc60.pdb | 45056 | 2016-10-30 |
3\test\test.dsp | 4261 | 2016-10-30 |
3\test\test.dsw | 516 | 2016-10-30 |
3\test\test.ncb | 41984 | 2016-10-30 |
3\test\test.opt | 48640 | 2016-10-30 |
3\test\test.plg | 1524 | 2016-10-30 |
3\test\test1.cpp | 2452 | 2016-10-30 |