7-6 laying oil well pipeline

7-6 Laying oil well pipelines

An oil company has n Well , To facilitate the transportation of oil , Plan to build an oil pipeline . According to the design requirements , There is a main pipe in the horizontal direction , A vertical branch pipeline is built for each oil well to lead to the main pipeline . Please design an algorithm to determine the location of the main pipeline , Minimize the total length of branch pipeline from all oil wells to the main pipeline . Tips ： The complexity is O(n) To pass all test cases .

Input format :
Each input file is a test case , The first line of each file gives a positive integer n(1≤n≤1000000), Indicates the number of wells , From the second line n Row data , Indicates the location of each well , Each line contains two integers separated by spaces , Represent the abscissa of each oil well respectively x(−10000≤x≤10000) And the vertical y(−10000≤y≤10000).

Output format :
Output the sum of the minimum length of the branch pipeline from each oil well to the main pipeline .

sample input :
Here's a set of inputs . for example ：

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

sample output :

9

Code ：

#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 3、 ... and