對于一維帶權(quán)郵局位置問題即找?guī)?quán)中位數(shù)。如下

// 一維郵局選址問題.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include<iostream>
#include<ctime>
#include<cmath>
#define N 100
using namespace std;

struct Node
{
double value;
double weight;
};
Node nodes[N];
//產(chǎn)生一個隨即下標，用其對應的數(shù)組元素作為比較標準(即一趟快速的主元）
int random(int m,int n)
{
srand((unsigned)time(NULL));
return m + (rand()%(n-m+1));
}
//一趟快速排序
int qartition(Node *nodes,int begin,int end)
{

int i = begin-1,j=begin;
double x = nodes[end].value;
while(j<end)
{
if(nodes[j].value<=x)
{
i++;
Node temp = nodes[i];
nodes[i]=nodes[j];
nodes[j]=temp;
}
j++;
}
Node temp = nodes[end];
nodes[end]=nodes[i+1];
nodes[i+1]=temp;
return i+1;
}
//一趟隨機化快速排序
int random_qartition(Node *nodes,int begin,int end)
{
int q = random(begin,end);
Node temp = nodes[end];
nodes[end]=nodes[q];
nodes[q]=temp;
return qartition(nodes,begin,end);
}
//隨機化快速排序
void random_fast_sort(Node *nodes,int begin,int end)
{
if(begin<end)
{
int p = random_qartition(nodes,begin,end);
random_fast_sort(nodes,begin,p-1);
random_fast_sort(nodes,p+1,end);
}
}
//得到帶權(quán)的中位數(shù)
Node GetMidWeight(Node *nodes,int begin,int end,double SumWeight)
{
double midSum = 0.0;
int i;
for(i=begin;i<=end;i++)
{
midSum+=nodes[i].weight;
if(midSum>=SumWeight/2)
break;
}
return nodes[i];
}
int _tmain(int argc, _TCHAR* argv[])
{
int cases;
cout<<"請輸入案例個數(shù)："<<endl;
cin>>cases;
while(cases--)
{
cout<<"請輸入數(shù)據(jù)個數(shù)："<<endl;
int n;
cin>>n;
int i;
double sum = 0.0;
cout<<"請輸入每一點值和其權(quán)值"<<endl;
for(i=0;i<n;i++)
{
cin>>nodes[i].value>>nodes[i].weight;
sum+=nodes[i].weight;
}
random_fast_sort(nodes,0,n-1);
cout<<"郵局位置為："<<endl;
Node node = GetMidWeight(nodes,0,n-1,sum);
cout<<node.value<<endl;
cout<<"總代價為："<<endl;
double sumValue = 0.0;
for(i=0;i<n;i++)
{
sumValue+=abs(nodes[i].value-node.value);
}
cout<<sumValue<<endl;
}
system("pause");
return 0;
}

<wbr><wbr><wbr>找出二維帶權(quán)郵局位置問題的最佳解答，其中所有的點都是(x,y)坐標對，并且點a(x1,y1)與點b(x2,y2)之間的距離是Manhattan距離：d(a,b)=|x1-x2|+|y1-y2|。</wbr></wbr></wbr>

對于二維帶權(quán)郵局位置問題可以轉(zhuǎn)化為一維郵局位置問題，分別求x、y的帶權(quán)中位數(shù)。見下篇《二維帶權(quán)郵局位置問題》

一維帶權(quán)郵局位置問題（找?guī)?quán)中位數(shù)）C++實現(xiàn)