算法设计练习作业，邮局选址问题，将自己写的分享，有问题请指正，希望共同学习。
关于邮局选址问题的理论知识就不赘述了，网上有讲解的。
#include <iostream>
#include <fstream>
#include <math.h>
using namespace std;
/*
*邮局选址问题，带权中位数
*输入的坐标不能相同，即x或y各自是n个不同的数，该程序为不同的整型数
*输入在文件input中，第一行为居民点个数，剩下行为（x,y,w）对，用空格分割
*输出文件为output，包括邮局坐标，带权的最短距离和
*/
int partition(int a[],float w[],int p,int r);
int partition2(int a[],float w[],int p,int r,int z);
void quicksort(int a[],float w[],int p,int r);
int select(int a[],float w[],int p,int r,int k);
int cut(int a[],float w[],int p,int r,int z) ;
int t=0;//外部变量，保存上一次划分得到的下标
int main()
{
fstream input,output;//输入输出流
int count=0;//居民点个数
int xk,yk;//所求的邮局坐标
float sum=0.0;//带权最短距离和
input.open("input_assign01_01.dat");
if(!input)
{
cout<<"error:unable to open input file!"<<endl;
return -1;
}
input>>count;
int *ax=new int[count];
int *ay=new int[count];//居民点x,y坐标数组
float *awx=new float[count];//居民点权值数组,对应下标为同一居民点
float *awy=new float[count];
for(int i=0;i<count;i++)
{
input>>ax[i]>>ay[i]>>awx[i];
awy[i]=awx[i];
}
xk=select(ax,awx,0,count-1,(count+1)/2);//计算xk，yk
yk=select(ay,awy,0,count-1,(count+1)/2);
for(i=0;i<count;i++)
{
sum+=awx[i]*abs(ax[i]-xk)+awy[i]*abs(ay[i]-yk);//求带权最短距离
}
output.open("output.txt");
output<<"邮局的坐标为："<<endl;
output<<"("<<xk<<","<<yk<<")"<<endl;
output<<"最短距离为："<<endl;
output<<sum;
input.close();
output.close();
delete []ax;
delete []ay;
delete []awx;
delete []awy;
return 0;
}
/*
*快速排序算法
*a为带排序数组，w为其权值数组，p为开始下标，r为结束下标
*功能是将a数组排序
*/
void quicksort(int a[],float w[],int p,int r)
{
if (p<r)
{int q=partition(a,w,p,r);
quicksort(a,w,p,q-1);
quicksort(a,w,q+1,r);
}
}
/*
*划分算法
*a为待划分数组，w为其权值数组，p为开始下标，r为结束下标，返回值为中心元下标
*功能是将数组进行划分，其中心元为数组最末端元素，划分后，比中心元小的元素在左边
*比中心元大的元素在右边，中心元在中间
*/
int partition(int a[],float w[],int p,int r)
{
int x=a[r];
int i=p-1;
for(int j=p;j<r;j++)
{
if(a[j]<=x)
{
i++;
swap(a[i],a[j]);
swap(w[i],w[j]);
}
}
swap(a[i+1],a[r]);
swap(w[i+1],w[r]);
return i+1;
}
/*
*划分算法
*a为待划分数组，w为其权值数组，p为开始下标，r为结束下标，z为中心元，返回值为中心元下标
*功能是将数组进行划分，中心元为指定元素z，划分后，比z小的元素在左边
*比z大的元素在右边，z在中间
*/
int partition2(int a[],float w[],int p,int r,int z)
{
int t=0;//记录a中等于z的元素的下标，便于将这个元素交换到中间
int i=p-1;
for(int j=p;j<=r;j++)
{
if(a[j]<=z)
{
i++;
if(a[j]==z)
{
t=i;
}
swap(a[i],a[j]);
swap(w[i],w[j]);
}
}
swap(a[i],a[t]);
swap(w[i],w[t]);
return i;
}
/*
*选择算法
*a为待选择的数组，w为其权值数组，p为开始下标，r为结束下标，k为待选择数组元素个数的中间值，返回值为带权中位数
*功能是选择带权中位数，先用中位数的中位数方法，求出n个不同的元素的中位数xk
*然后计算小于xk的元素的权值和wl,大于xk的元素的权值和wr
*如果wl<0.5 and wr<=0.5，则xk即为所求
*如果wl>=0.5，则对xk左边的数组元素递归调用select函数，否则对xk右边的数组元素递归调用select函数
*/
int select(int a[],float w[],int p,int r,int k)
{
float wl=0.0,wr=0.0;//中位数的权值和wl，wr
if (r-p<5)
{
quicksort(a,w,p,r);
// return a[p+k-1];
for(int m=p;m<p+k-1;m++)
{
wl+=w[m];//比x小的元素的权值和
}
for(m=p+k;m<=r;m++)
{
wr+=w[m];//比x大的元素的权值和
}
if(wl<0.5 && wr<=0.5)
return a[p+k-1];//符合带权中位数的条件返回
else if(wl>=0.5)
{
w[p+k-1]+=wr;//处理x的左端
return select(a,w,p,p+k-1,(k+1)/2);
}
else
{
w[p-k+1]+=wl;//处理x的右端
return select(a,w,p+k-1,r,(r-p-k+3)/2);
}
}
for (int i=0;i<(r-p+1)/5;i++)//分组排序，将中位数交换到数组前端
{
quicksort(a,w,p+5*i,p+5*i+4);
swap(a[p+5*i+2],a[p+i]);
swap(w[p+5*i+2],w[p+i]);
}
int x=select(a,w,p,p+(r-p+1)/5-1,(((r-p+1)/5)+1)/2);//中位数的中位数
i=partition2(a,w,p,r,x);//计算x前半区元素个数
int j=i-p+1;
for(int m=t;m<i;m++)
{
wl+=w[m];//比x小的元素的权值和
}
for(m=i+1;m<=r;m++)
{
wr+=w[m];//比x大的元素的权值和
}
if(wl<0.5 && wr<=0.5)
return a[i];//符合带权中位数的条件返回
else if(wl>=0.5)
{
w[i]+=wr;//处理x的左端
t=i;
return select(a,w,p,i,(j+1)/2);
}
else
{
w[i]+=wl;//处理x的右端
t=i;
return select(a,w,i,r,(r-i+1+1)/2);
}
}
