shengqiang's blog

输油管道最小总长度求解

 
  • 2017年 07月10日

##大致思路：

  1. 通过查询相关资料后，发现了最优总长度为各个油井到主输油管道的最短路径与中位数的距离之和
  2. 利用分治法思想，将查找区间慢慢缩小
  3. 首先在n个数据中查找第n/2+1小的数据，即中位数
  4. 将n个数据分成两个集合，一个左子集，剩余的为右子集
  5. 若在左子集查找到第n/2+1小的数据有n/2个，则找到中位数
  6. 若在左子集查找到第n/2+1小的数据小于n/2个，则舍弃左子集，在右子集查找，依次递归。
  7. 若在左子集查找到第n/2+1小的数据大于n/2个，则舍弃左子集中的第一个元素，并继续在该左子集查找，依次递归。

##主函数:

  1. 定义变量油井数量n，中位数mid,总长度sum
  2. 提示用户输入油井的总数量，并依次输入Y坐标
  3. 调用函数FindMid(0, n – 1, n / 2 + 1)，返回中位数
  4. 计次循环，求出sum的最终值，并打印输出。

##FindMid (…)函数:

  1. 定义变量左子集个数nleft，左区间i。右区间j，中间变量temp
  2. 用i,j分别从左到右，从右到左进行遍历使比a[s]小或等于a[s]的都在左子集中，用nleft计数
  3. 若左子集的个数等于t-1,则找到了第t小的数a[s]
  4. 若左子集的个数nleft小于t-1，则舍弃左子集和a[s],找右子集中第t-nleft-1个
  5. 若nleft+1>t,在左子集中继续找第t小的数

##关键代码：

// Tubing.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include<stdio.h>
#include<stdlib.h>
#define N 1000//最大油井数目
int  y[N];//y坐标

int FindMid(int s, int e, int t)//从a[s]到a[e],找第t小的
{
    int nleft = 0;
    int i, j = e;
    int temp;
    //用i,j分别从左到右，从右到左进行遍历使比a[s]小或等于a[s]的都在左子集中，用nleft计数
    for (i = s + 1; i <= j; i++)
    {
        if (y[i] <= y[s])
            nleft++;//左子集中的个数加一
        else
        {
            for (; j>i; j--)//加快查找速度
                if (y[j] <= y[s])
                {
                    temp = y[i];
                    y[i] = y[j];
                    y[j] = temp;
                    nleft++;//左子集个数++
                }
        }
    }

    //左子集的个数等于t-1,则找到了第t小的数a[s]
    if (nleft + 1 == t)
        return y[s];

    //左子集的个数nleft小于t-1，则舍弃左子集和a[s],找右子集中第t-nleft-1个
    else if (nleft + 1<t)
        FindMid(s + nleft + 1, e, t - nleft - 1);

    //nleft+1>t,在左子集中继续找第t小的数
    else
        FindMid(s + 1, i - 1, t);
}

int main()
{
    int n, mid, sum = 0;
    printf("请输入油井数量N:");
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        printf("请依次输入各个油井的y坐标，无需输入x坐标\n");
        scanf("%d", &y[i], &y[i]);//由于x坐标没用，为了节省空间，只输入y坐标
    }

    //若是奇数个，则中位数位于第n/2+1小的位置 	
    //若是偶数个，则中位数位于第n/2或者n/2+1，而此时管道位置
    //可以取任意一个，所以，输入n/2+1可以满足任意条件
    mid = FindMid(0, n - 1, n / 2 + 1);//获取中位数
                                         						
    for (int i = 0; i<n; i++)
        sum = sum + abs(y[i] - mid);//距离的绝对值
    printf("长度%d\n", sum);
    system("pause");
    return 0;
}
搜索