pipe_search_k.cpp

给定n口油井的位置,编程计算各油井到主管道之间的输油管道最小长度总和。

#include<iostream>
#include<fstream>
#include<cmath>
template<class T>
class Select_k{
    private:
        T *data;
        int n;
        void sel_sort(int low,int up);
        int partition(int m,int p);
        void interchange(int i,int j)
        {T temp;temp=data[i];data[i]=data[j];data[j]=temp;}
        int ceil(int a,int b)
        {if(!(a%b))return a/b;else return (a/b+1);}
        T select(int k,int low,int up);
    public:
        Select_k(int m):n(m){data=new T[m];}
        ~Select_k(){delete []data;}
        void input(std::ifstream &fin);        
        T scan(int k,int low,int up){return data[select(k,low,up)];}
        T get_least(T mid);
};
template<class T>
void Select_k<T>::sel_sort(int low,int up)
{
    T temp;
    for(int i=low;i<up;i++){
        int k=i;
        for(int j=i+1;j<=up;j++)
            if(data[k]>data[j])k=j;
        if(k!=i)
            interchange(k,i);
    }
}
template<class T>
int Select_k<T>::partition(int m,int p)
{
    T v=data[m],temp;int i=m,j=p;
    do{
        do i++;
        while(data[i]<v);
        do j--;
        while(data[j]>v);
        if(i<j)
            interchange(i,j);
    }while(i<j);
    data[m]=data[j];data[j]=v;return j;
}
template<class T>
T Select_k<T>::select(int k,int low,int up)
{
    int r=20;
    do{
        int t=up-low+1;
        if(t<=r){
            sel_sort(low,up);
            return data[low+k-1];
        }
        for(int i=1;i<=t/r;i++){
            sel_sort(low+(i-1)*r,low+i*r-1);
            interchange(low+i-1,low+(i-1)*r+ceil(r,2)-1);
        }
        int j=select(ceil(t/r,2),low,low+t/r-1); //查找中值的中值
        interchange(low,j);
        j=partition(low,up+1);
        if(k==j-low+1)return j;
        else if(k<j-low+1)up=j-1;
        else{k-=(j-low+1);low=j+1;}
    }while(1);
}
template<class T>
void Select_k<T>::input(std::ifstream &fin)
{
    T temp;
    for(int i=0;i<n;i++)fin>>temp>>data[i];
}
template<class T>
T Select_k<T>::get_least(T mid)
{
    T least=0;
    for(int i=0;i<n;i++)
        least+=abs(data[i]-mid);
    return least;
}
using namespace std;
int main()
{
    ifstream fin("input.txt");
    ofstream fout("output.txt");
    if(!fin.is_open()){
        fout<<"the input.txt is not exist\n";
        exit(1);
    }
    int n;
    while(fin>>n){
        Select_k<int> s(n);        
        s.input(fin);
        int mid=s.scan(n/2+1,0,n-1);
     //   fout<<mid<<endl;
        fout<<s.get_least(mid)<<endl;
    }
    fin.close();
    fout.close();
    return 0;
}