7-6 铺设油井管道

7-6 铺设油井管道

某石油公司有n口油井，为方便输送石油，计划修建输油管道。根据设计要求，水平方向有一条主管道，每口油井修一条垂直方向的支线管道通向主管道。请设计一种算法确定主管道的位置，使得所有油井到主管道之间的支线管道长度的总和最小。提示：复杂度为O(n)才能通过所有测试用例。

输入格式:
每个输入文件为一个测试用例，每个文件的第一行给出一个正整数n(1≤n≤1000000)，表示油井数量，从第二行起的n行数据，表示每口油井的位置，每行包含以空格分隔的两个整数，分别表示每口油井的横坐标x(−10000≤x≤10000)和纵坐标y(−10000≤y≤10000)。

输出格式:
输出各油井到主管道之间的支管道最小长度总和。

输入样例:
在这里给出一组输入。例如：

4
-1 1
2 2
5 -1
-3 7

输出样例:

9

代码：

#include <stdio.h>
#include <stdlib.h>
#include<math.h>
int n;
int a[1001010];
int k;
int mid;
void fid(int left,int right)
{
    
    int temp=a[left];
    int i=left;
    int j=right;
    if(i>j)
        return;
    while(i<j)
    {
    
        while(i<j&&a[j]>temp)
            j--;
        a[i]=a[j];
        while(i<j&&a[i]<=temp)
            i++;
        a[j]=a[i];
    }
    a[i]=temp;
    if(i==k)
        mid=a[i];
    else if(i>k)
        fid(left,i-1);
    else
        fid(i+1,right);
    return ;
}
int main()
{
    
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
    
        int x;
        scanf("%d%d",&x,&a[i]);
    }
    if(n%2==0)
        k=n/2;
    else
        k=n/2+1;
    fid(1,n);
    long long sum=0;
    for(int i=1;i<=n;i++)
        sum+=abs(a[i]-mid);
    printf("%lld",sum);
    return 0;
}

202206222114三