C++分治算法------士兵站队问题----邮局选址问题

阳光穿透心脏的1/2处 2024-03-22 11:31 117阅读 0赞

**目录**

C++分治算法------士兵站队问题

实验题目

【样例输出】8

代码：

邮局选址问题

代码

--------------------

## C++分治算法------士兵站队问题 ##

### 实验题目 ###

在一个划分成网格的操场上，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。  
【输出形式】  
将计算结果:输出的第1 行中的数是士兵排成一行需要的最少移动步数。

【样例输入】  
5  
1 2  
2 2  
1 3  
3 -2  
3 3

#### 【样例输出】   8 ####

> 2.的分析：
> 
> 做过输油管道问题得同学可能有点思路，但是现在是二维坐标，不再是一维坐标了，多了一维，那么问题就要变得复杂了。现在看分析：
> 
> Y轴上：(假设现在有n个士兵)：
> 
> 可以把所有士兵得y坐标看成一个输油管道问题，即找一个坐标Y\_mid，使得所有y坐标道该坐标的距离之和最小。显然sum1 = |y0-Y\_mid| + |y1-Y\_mid| + |y2-Y\_mid|....|yn-1-Y\_mid|。 经过证明Y\_mid就是y坐标的中位数，注意中位数，不是数学意义上的中位数，是将n个数按序排序，第n/2大的数，即a\[n/2\]。
> 
> X轴上。这里就有点难以分析了。
> 
> 假设现在排序后的x坐标为x0,x1,x2,x3.....xn-1，而最终士兵站好的坐标为x'0,x'1,x'2.....x'n-1。那么需要移动的步数就是sum2 = |x0-x'0| + |x1-x'1| + |x2-x'2|....+| xn-1-x'n-1|。 而我们直到士兵排好序后是连续的，所以上面公式可以写成这样，sum2 = |x0-x'0| + |x1-(x'0+1)| + |x2-(x'0+2)|....+| xn-1-(x'0+n-1)|。 现在就和那个输油管道问题是一样的了。但是现在这个公式还不够直观，现在我们把公式再进行转化 sum2 = |x0-x'0| + |(x1-1)-x'0)| + |(x2-2)-x'0|....+| (xn-1-(n-1))-x'0)|。 很显然这个x'0就是数组x坐标的中位数。
> 
> 则最小移动步数为 sum1+sum2。

####    代码： ####

#include<iostream>
    #include<algorithm>
    #define ll long long 
    using namespace std;
    
    ll n, a, b;
    int x[20002], y[20002];
    
    int abss(int a, int b)
    {
        if (a > b)  return a - b;
        else  return b - a;
    }
    
    int main()
    {
        cin>>n;
        for (int i = 0; i < n; ++i)
            cin >> x[i] >> y[i];
        sort(x, x + n);
        sort(y, y + n);
        for (int i = 0; i < n; ++i)  x[i] -= i;
        sort(x, x + n);
        for (int i = 0; i < n; ++i)
        {
            a += abss(x[n / 2], x[i]);
            b += abss(y[n / 2], y[i]);
        }
        cout<<a+b;
        return 0;
    }

#include<stdio.h>
    #include<math.h>
    #include<stdlib.h>
    #define Max 10000
    int Compare(const void* e1, const void* e2)//定义函数比较
    {
    	return (int)*((int*)e1) - (int)*((int*)e2);
    }
     
    int add(int a[], int n,int mid)
    {
    	int sum = 0;
    	for (int i = 0; i < n; i++)
    	{
    		sum += abs(a[i]-mid);
    	}
    	return sum;
    }
     
    int main()
    {
    	int x[Max] = { 0 }, y[Max] = { 0 };
    	int n = 0;
    	scanf("%d", &n);
    	int i = 0;
    	for (i = 0; i < n; i++)
    	{
    		scanf("%d%d", &x[i], &y[i]);
    	}
    	qsort(x, n, sizeof(x[0]), Compare);
    	qsort(y, n, sizeof(y[0]), Compare);
    	for (i = 0; i < n; i++)//这是x轴上的坐标移动的最终位置，是根据公式求得的
    	{
    		x[i] = x[i] - i;
    	}
    	qsort(x, n, sizeof(x[0]), Compare);
    	int Y_mid = y[n / 2], X_mid = x[n / 2];
    	int y_sum = 0, x_sum = 0;
    	y_sum = add(y, n, Y_mid);	
    	x_sum = add(x, n, X_mid);
    	printf("%d\n", x_sum + y_sum);
    	return 0;
    }

## 邮局选址问题 ##

在一个按照东西和南北方向划分成规整街区的城市里，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 10  
1 2  
2 2  
1 3  
3 -2  
3 3

--------------------

> 问题描述：
> 
> 在一个按照东西和南北方向划分成规整街区的城市里，n个居民点散乱地分布在不同的街区中。用x 坐标表示东西向，用y坐标表示南北向。各居民点的位置可以由坐标(x,y)表示。街区中任意两点(x1,y1)和(x2,y2)之间的距离可以用数值|x1-x2|+|y1-y2|来度量。
> 
> 邮局选址问题是，居民们希望在城市中选择建立邮局的最佳位置，使n个居民点到邮局的距离总和最小。
> 
> 算法思想：
> 
> 设邮局的位置为(x,y).那么所有居民点东西向距邮局x的距离和sumX=|x-x1|+|x-x2|+…+|x-xn|。由中位数定理可知,x为所有居民点东西向坐标的中位数。同理可知，y为所有居民点南北向坐标的中位数。所以，问题就转化为求一个无序数组的中位数（高效求解：线性时间选择）。
> 
> 线性时间选择问题：给定线性集中n个元素和一个整数k，求这n个元素的第k小的元素，当k=(n+1)/2时，称为找中位数。
> 
> 如果能在线性时间内找到一个划分基准，使得按这个基准划分出的两个子数组的长度都至少为原数组长度的ε倍（0<ε<1），那么在最坏情况下用O(n)时间可以完成选择任务。
> 
> 划分基准的选择步骤:
> 
> 第一，将n个元素划分成⌈n/5⌉，每组5个元素，最后一组可能少于5个元素。对每组的元素进行排序，并取出每组元素的中位数，共⌈ n/5⌉个。
> 
> 第二，递归调用该函数，求⌈ n/5⌉个中位数的中位数，如果⌈ n/5⌉为偶数，求两个中间数较大的一个，以此作为基准进行划分。
> 
> 找到基准后，可以以此基准进行一趟快速排序，将数组划分成两个子数组。然后比较左边子数组个数与整数k的大小，确定第k小元素在哪一个子数组中，达到减小问题规模的目的。最后，递归调用该函数，求出第k小元素。  
>

### 代码： ###

void Swap(int &a, int &b){
    	int temp = a;
    	a = b;
    	b = temp;
    }
     
    //当元素较少时，可以选择冒泡排序求解中位数
    void BubbleSort(int *a, int p, int r){
    	int change = 1;
    	for(int i = r;i>p && change;--i){
    		change = 0;
    		for(int j = p;j<i;j++){
    			if(a[j]>a[j+1]){
    				Swap(a[j],a[j+1]);
    				change = 1;
    			}
    		}
    	}
    }
     
    //快速排序
    int QuickSort(int *a, int p, int r, int partition){
    	int i = p-1, j = r+1;
    	while(1){
    		while(a[++i] < partition && i < r);
    		while(a[--j] > partition);
    		if(i >= j) break;
    		Swap(a[i],a[j]);
    	}
    	a[j] = partition;
    	return j;
    }
     
    //求第k小元素
    int Select(int *a, int p, int r, int k){
    	if(r-p<75){    //元素个数小于75，使用冒泡排序
    		BubbleSort(a,p,r);
    		return a[p+k-1];
    	}
    	for(int i = 0;i<=(r-p-4)/5;i++){
    		BubbleSort(a,p+i*5,p+i*5+4);    //先把每组的5个元素排好序
    		Swap(a[p+i],a[p+i*5+2]);        //将每组的中位数交换到数组的前面
    	}
    	int x = Select(a, p, p+(r-p-4)/5, p+(r-p-4)/10); //求解每组中位数的中位数x
    	int i = QuickSort(a,p,r,x),j = i-p+1;    //以x作为快排的基准，达到成倍减小数组规模的目的
    	if(k<=j){
    		return Select(a,p,r,k);
    	}else{
    		return Select(a,i+1,r,k-j);
    	}
    }

--------------------

###    代码 ###

#include <bits/stdc++.h>
    #define INF 0x3f3f3f3f
    using namespace std;
    
    const int MAXN = 500010;
    int xPos[MAXN], yPos[MAXN];
    int sortedX[MAXN], sortedY[MAXN];
    
    // 计算区间 [l, r] 内的居民点到邮局距离之和
    int calcDist(int l, int r, int mid) {
        int sum = 0;
        for(int i = l; i <= r; i++) 
            sum += abs(sortedX[mid] - sortedX[i]) + abs(sortedY[mid] - yPos[i]);
        return sum;
    }
    
    // 对坐标数组进行排序并返回中位数的下标
    int sortAndFindMid(int l, int r, int len) {
        for(int i = l; i <= r; i++) {
            sortedX[i] = xPos[i];
            sortedY[i] = yPos[i];
        }
        sort(sortedX+l, sortedX+r+1); // 按 x 坐标排序
        sort(sortedY+l, sortedY+r+1); // 按 y 坐标排序
        int midX = sortedX[l+(r-l)/2];
        int midY = sortedY[l+(r-l)/2];
        for(int i = l; i <= r; i++) {
            if(xPos[i] == midX) sortedX[i] = sortedX[l+(r-l)/2];
            if(yPos[i] == midY) sortedY[i] = sortedY[l+(r-l)/2];
        }
        return l+(r-l)/2;
    }
    
    int solve(int l, int r, int len) {
        if(l >= r) return 0; // 只有一个点则不需要建邮局
        int mid = sortAndFindMid(l, r, len);
        int sumDist = calcDist(l, r, mid);
        return sumDist + solve(l, mid-1, mid-l) + solve(mid+1, r, r-mid);
    }
    
    int main() {
        int n;
        scanf("%d", &n);
        for(int i = 0; i < n; i++) 
            scanf("%d %d", &xPos[i], &yPos[i]);
        printf("%d\n", solve(0, n-1, n));
        return 0;
    }

> 这段代码实现了邮局选址问题的分治法解法，具体实现如下：
> 
> 1.  定义好变量和数组：定义了常量MAXN（居民点最大数量），xPos、yPos、sortedX、sortedY四个整型数组。
> 2.  编写了calcDist函数，用于计算区间 \[l, r\] 内的居民点到邮局距离之和。其中mid是已排序后的x坐标数组中间值的下标，通过遍历y坐标数组，在加上每个点到邮局的距离即可求出该区间内所有居民点到邮局的总距离。
> 3.  编写sortAndFindMid函数，用于对坐标数组进行排序并返回中位数的下标。该函数首先将x和y坐标分别复制一份到sortedX和sortedY数组中，然后对其进行排序。接着，获取排序后中间位置的数值，并将原数组中与该数值相同的元素都替换成排序后的中位数。然后返回中位数的下标。
> 4.  编写solve函数，用于递归求解选址问题。如果区间长度为1，则直接返回0；否则，先使用sortAndFindMid函数找到中位数，然后使用calcDist函数计算该区间的居民点到该中位数的邮局的距离。接着，再将左右两个子区间递归调用solve函数进行求解，并将结果相加返回。
> 5.  在main函数中，首先读入输入的居民点数量n以及每个居民点的坐标，然后使用solve函数计算出邮局位置，并输出答案。
> 
> 整体思路是通过对坐标进行排序，以及不断缩小问题规模，从而实现了快速求解邮局选址问题。