pipe.cpp

输油管道问题,算法

#include<iostream>
#include<cstdlib>
#include<math.h>
using namespace std;
void swap(int &a,int &b)
{
   int temp;
   temp=a;
   a=b;
   b=temp;
}
int Partition(int a[],int p,int r)
{
 int i=p;
 int j=r+1;
 int x=a[p];
while(1)
{
while(a[++i]<x&&i<r);
while(a[--j]>x);
if(i>=j) break;
swap(a[i],a[j]);
}
 a[p]=a[j];
 a[j]=x;
return j;
}
int   MinTotal(int a[],int  k,int  n)
{int  total=0;
int  temp;
for(int i=0;i<n;i++)
{ 
 temp=abs(a[i]-a[k]);
 total+=temp;
}
return total;
}

void  QuickSort(int a[],int p,int r)
{   int q;
   if(p<r)
  {q=Partition(a,p,r);
  QuickSort(a,p,q-1);
  QuickSort(a,q+1,r); 
 }
}
int main()
{
 
    int  a[10000],b[10000];
    int n,i,k,k1,k2;
    int  Mintotal;
    int Mid;
    freopen("pipe.in","r",stdin);
	freopen("pipe.out","w",stdout);
//cout<<"请输入n值:";
cin>>n;
  for(i=0;i<n;i++)
  {
   cin>>a[i];
   cin>>b[i];
  }
QuickSort(b,0,n-1);
/*for(int j=0;j<n;j++)
{
        cout<<b[j]<<" ";
        } 
        cout<<endl;*/
if(n%2==1)
{ k=n/2;
 Mintotal=MinTotal(b,k,n);
 Mid=b[k];
}
else
{
k1=n/2;
k2=n/2-1;
int  Mintotal_1=MinTotal(b,k1,n);
int  Mintotal_2=MinTotal(b,k2,n);
if((Mintotal_1-Mintotal_2)<0)
  {
  Mintotal=Mintotal_1;
  Mid=b[k1];
}
else
  {
  Mintotal=Mintotal_2;
  Mid=b[k2];
}
 } 
// cout<<"中位点值为："<<Mid<<endl;   
 cout/*<<"最小值为："*/<<Mintotal<<endl;
 //system("PAUSE");
 return 0;
}