实验三
一、 实验目的
1. 理解分治法的基本思想 2. 掌握分治法的递归实现方法 3. 学习分治策略设计技巧
二、实验题目
1． 邮局选址问题
在一个按照东西和南北方向划分成规整街区的城市里， n 个居民点散乱地分
布在不同的街区中。用 x 坐标表示东西向，用 y 坐标表示南北向。各居民点的
位置可以由坐标(x,y) 表示。街区中任意 2 点(x1,y1) 和(x2,y2) 之间的距离可以用
数值|x1-x2|+|y1-y2| 度量。 居民们希望在城市中选择建立邮局的最佳位置，使
n 个居民点到邮局的距离总和最小。
给定 n 个居民点的位置，编程计算 n 个居民点到邮局的距离总和的最小值。
【输出格式】: 输入由多组数据组成。
每组数据输入的第 1 行是居民点数 n，1≤n≤10000。接下来 n 行是居民点
的位置，每行 2 个整数 x 和 y，-10000≤x，y≤10000。
【输出格式】: 对应每组输入，输出的第 1 行中的数是 n 个居民点到邮局
的距离总和的最小值。
【 样 例 】 标准输入 标准输出 .
5 1
1 2
2 2
1 3
3 -2
3 3
2． 士兵站队问题
在一个划分成网格的操场上，n 个士兵散乱地站在网格点上。网格点用整数
坐标(x,y)表示。士兵们可以沿网格边往上、下、左、右移动一步，但在同一时刻
任一网格点上只能有一名士兵。按照军官的命令，士兵们要整齐地列成一个水平
队列，即排列成(x,y),(x+1,y),…,(x+n-1,y)。如何选择 x 和 y 的值才能使士兵们以最
少的总移动步数排成一行。
编程计算使所有士兵排成一行需要的最少移动步数。
【输入格式】：第 1 行是士兵数 n，1≤n≤10000。接下来 n 行是士兵的初始
位置，每行有 2 个整数 x 和 y，-10000≤x，y≤10000。
【输出格式】：一个数据，即士兵排成一行需要的最少移动步数。
【 样 例 】 标准输入 标准输出 . 5 8
1 2
2 2
1 3
3 -2
3 3
#include<stdio.h>
#include<stdlib.h>
#define N 10000
int a[N], b[N];//全局变量，a[i]表示横坐标,b[i]表示纵坐标
void SwapAij(int array[], int i, int j)
{//交换下标为array[i]和array[j]的两个下标
int temp;
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
int SearchMid(int array[], int s, int e, int t)
{//从array[s]到array[e]中找第t小的，用类似于快速排序算法思想，枢轴就是a[s]
int nleft = 0;//用于记数，记录比a[s]小的数的个数
int i;
int j = e;
for (i = s + 1; i <= j; i++)
{
if (array[i] <= array[s])
{
nleft++;//左边的数总个数加1
}
else
{//如果a[i]>a[s],就从a[e]到a[s]从右到左开始找，
//当找到一个比a[s]小的数后，让他与刚才上一级那个比a[s]大的数交换
for (; j > i; j--)
{
if (array[j] <= array[s])
{
SwapAij(array, i, j);
nleft++;//交换后左边的数加1
}
}
}
}
if (nleft + 1 == t)
return array[s];
else if (nleft + 1 < t)//左边nleft不够,从右边找
SearchMid(array, s + nleft + 1, e, t - nleft - 1);
else//左边的多，继续找
SearchMid(array, s + 1, i - 1, t);
}
int main()
{
int n, mid1, mid2, sum1 = 0, sum2 = 0, sum = 0;
printf("输入居民点的个数：");
scanf_s("%d", &n);
printf("输入居民点的横纵坐标:\n");
for (int i = 0; i < n; i++)
scanf_s("%d %d", &b[i], &a[i]);//输入居民点的坐标
mid1 = SearchMid(a, 0, n - 1, n / 2 + 1);//求横坐标的中位数即 从a[0]到a[n - 1]找第n / 2 - 1小的
mid2 = SearchMid(b, 0, n - 1, n / 2 + 1);//求纵坐标的中位数即 从a[0]到a[n - 1]找第n / 2 - 1小的
printf("纵坐标中位数mid1=%d\n", mid1);
printf("横坐标中位数mid2=%d\n", mid2);
for (int i = 0; i < n; i++)
sum1 += abs(a[i] - mid1);//所有油井位置的纵坐标减去中位数的绝对值即为最小长度总和
for (int i = 0; i < n; i++)
sum2 += abs(b[i] - mid2);//所有油井位置的横坐标减去中位数的绝对值即为最小长度总和
sum = sum1 + sum2;
printf("x轴上最小距离是%d\n", sum1);
printf("y轴上最小距离是%d\n", sum2);
printf("n个居民点到邮局的距离总和最小总和是：%d\n", sum);
system("pause");
return 0;
}
士兵站队问题分析：
本题实质就是求 X 和 Y 方向总共需要移动的最少步数。假设n 个士兵的坐标分别为（X1,Y1）,(X2,Y2),(X3,Y3)……（Xn-1,Yn-1),(Xn,Yn)。
对于 Y 方向来说，假如最后所有士兵都在y坐标为Y的坐标上，则即使求|Y1-Y|+|Y2-Y|+|Y3-Y|+……|Yn-1-Y|+|Yn-Y|的最小值，可以用数学方法证明 Y 值即是Y1，Y2，Y3……Yn-1,Yn的中位数，据此可以求出在Y方向需要移动的总步数；对于X方向，先对所有的X坐标从小到大排序，排序后，为了放便描述，我们依然用X1，X2，X3……Xn-1，Xn代表士兵排序后的位置，假如最后所有士兵站的位置为X，X+1，X+2……X+n-1，那么即是求|X1-X|+|X2-(X+1)|+|X3-(X+2)|+……|Xn-(X+n-1)|的最小值，即|X1-X|+|（X2-1）-X|+|（X3-2）-X|+……|（Xn-（n-1））-X|，X即为X1,X2-1,X3-2……Xn-(n-1)的中位数，据此可以求得X方向的最小移动步数。
#include<stdio.h>
#include<stdlib.h>
#define N 10000
int a[N], b[N];//全局变量，a[i]表示横坐标,b[i]表示纵坐标
void SwapAij(int array[], int i, int j)
{//交换下标为array[i]和array[j]的两个下标
int temp;
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
int SearchMid(int array[], int s, int e, int t)
{//从array[s]到array[e]中找第t小的，用类似于快速排序算法思想，枢轴就是a[s]
int nleft = 0;//用于记数，记录比a[s]小的数的个数
int i;
int j = e;
for (i = s + 1; i <= j; i++)
{
if (array[i] <= array[s])
{
nleft++;//左边的数总个数加1
}
else
{//如果a[i]>a[s],就从a[e]到a[s]从右到左开始找，
//当找到一个比a[s]小的数后，让他与刚才上一级那个比a[s]大的数交换
for (; j > i; j--)
{
if (array[j] <= array[s])
{
SwapAij(array, i, j);
nleft++;//交换后左边的数加1
}
}
}
}
if (nleft + 1 == t)
return array[s];
else if (nleft + 1 < t)//左边nleft不够,从右边找
SearchMid(array, s + nleft + 1, e, t - nleft - 1);
else//左边的多，继续找
SearchMid(array, s + 1, i - 1, t);
}
int Partition(int array[], int low, int high)
{
int pivokey;
pivokey = array[low];
while (low < high)
{
while (low < high&&a[high] >= pivokey)
{
high--;
}
a[low] = a[high];
while (low < high&&a[low] <= pivokey)
{
low++;
}
a[low] = pivokey;
return low;
}
}
void QSort(int array[], int low, int high)
{
int pivotloc;
if (low < high)
{
pivotloc = Partition(array, low, high);
QSort(array, low, pivotloc - 1);
QSort(array, pivotloc + 1, high);
}
}
int main()
{
int n, mid1, mid2, sum1 = 0, sum2 = 0, sum = 0;
printf("输入士兵的个数：");
scanf_s("%d", &n);
printf("输入士兵的横纵坐标:\n");
for (int i = 0; i < n; i++)
scanf_s("%d %d", &a[i], &b[i]);//输入居民点的坐标
QSort(a, 0, n - 1);
for (int i = 0; i < n; i++)
{//排完序后减i，确定最终位置
a[i] = a[i] - i;
}
mid1 = SearchMid(a, 0, n - 1, n / 2 + 1);//求排完序后横坐标的中位数即 从a[0]到a[n - 1]找第n / 2 - 1小的
mid2 = SearchMid(b, 0, n - 1, n / 2 + 1);//求纵坐标的中位数即 从a[0]到a[n - 1]找第n / 2 - 1小的
printf("横坐标中位数mid1=%d\n", mid1);
printf("纵坐标中位数mid2=%d\n", mid2);
for (int i = 0; i < n; i++)
sum1 += abs(a[i] - mid1);//所有油井位置的纵坐标减去中位数的绝对值即为最小长度总和
for (int i = 0; i < n; i++)
sum2 += abs(b[i] - mid2);//所有油井位置的横坐标减去中位数的绝对值即为最小长度总和
sum = sum1 + sum2;
printf("x轴上最小距离是%d\n", sum1);
printf("y轴上最小距离是%d\n", sum2);
printf("n个士兵总和最小是：%d\n", sum);
system("pause");
return 0;
}