庞果网之建立信号基站

/*********************************
*   日期：2013-11-14
*   作者：SJF0115
*   题号: 题目 建立信号基站
*   来源：http://hero.pongo.cn/Question/Details?ID=81&ExamID=79
*   结果：AC
*   来源：庞果网
*   总结：
**********************************/
#include<iostream>
#include<stdio.h>
#include<string>
using namespace std;


double bestDistance(int n, const int *x, const int *y){
	int i,index,temp,j;
	double result,min1 = 0,min2 = 0,min3 = 0,min4 = 0;
	int *sum,*difference;
    sum = (int *)malloc(sizeof(int) * n);
    difference = (int *)malloc(sizeof(int) * n);
	//计算和差
	for(i = 0;i < n;i++){
		sum[i] = x[i] + y[i];
		difference[i] = x[i] - y[i];
	}
	//排序（从小到大）
	for(i = 0;i < n - 1;i++){
        for(j = i + 1;j < n;j++){
            if(sum[i] > sum[j])
            {
                temp = sum[i];
                sum[i] = sum[j];
                sum[j] = temp;
            }
        }
    }
	for(i = 0;i < n - 1;i++){
        for(j = i + 1;j < n;j++){
            if(difference[i] > difference[j])
            {
                temp = difference[i];
                difference[i] = difference[j];
                difference[j] = temp;
            }
        }
    }

	index = n / 2 - 1;
	for(i = 0;i <= index;i++){
		min1 += sum[i];
		min2 += difference[i];
	}
	//判断n奇偶性
	if(n % 2 == 0){
		index = n / 2;
	}
	else{
		index = n / 2 + 1;
	}
	for(i = index;i <= n-1;i++){
		min3 += sum[i];
		min4 += difference[i];
	}
	result = (min3 - min1 + min4 - min2) / 2.0;
	return result;
}

int main()
{   
	/*int i,n;
	int x[101],y[101];
	while(scanf("%d",&n) != EOF){
		for(i = 0;i < n;i++){
			scanf("%d %d",&x[i],&y[i]);
		}
		printf("%lf\n",bestDistance(n,x,y));
	}*/
	int x[] = {858442934,-161749718,-55910439,347569202,-660170269,-982075453,-860790164,947179323,312298821,-285196111,967545126,-777105315,-630974471,-713895350,745616673,840630174,-597730146,-205693089,24677872};
	int y[] = {449535070,160026431,705809990,121634879,648304545,-392329548,-447666131,-829918127,926665890,943182185,601133076,-848803337,89719473,-586785144,832132969,-111884761,-556530757,65860874,978639057};
	int n = 19;
	printf("%lf\n",bestDistance(n,x,y));
    return 0;
}

【解析】：

解题的关键在于如何处理max{|X – x|, |Y – y|}，可以通过分段函数讨论来证明，max{|x1-x2|,|y1-y2|},等价于（|x1+y1-x2-y2|+|x1-y1-(x2-y2)|）/2；

　　假设信号基站的坐标是(X , Y)，那么他与其他坐标的距离为max{|X – x1|, |Y – y₁|} = （|X+Y-x₁-y₁|+|X-Y-(x₁-y₁)|）/2, ……，（|X+Y-x_n-y_n|+|X-Y-(x_n-y_n)|）/2;也就是最短距离

　　bestDistance = 1/2  * （|X+Y-(x₁+y₁)| + |X-Y-(x₁-y₁)| + |X+Y-(x₂₊y₂)| + |X-Y-(x₂-y₂)| +……+ |X+Y-(x_n+y_n)|+|X-Y-( x_n-y_n)|） -- (1-1)

　　其中，x₁+y_{1 、}x₁-y₁  、 x₂₊y_{2 、} x₂-y_{2 、……、}x_n+y_{n  、} x_n-y_n 均为常数, 通过题目所给的数组可以容易得到这些值

　　假设 U(X, Y) = X + Y ,       V(X, Y) = X - Y ;可以得到

　　bestDistance =  1/2  *(|U - U₁| + |V - V₁| + |U - U₂| + |V - V₂| + ……+ |U - U_n| + |V - V_n|)    -- (1 - 2)

　　　　　= 1/2  *【(|U - U₁| + |U - U₂| + ……+ |U - U_n|) + (|V - V₁|  + |V - V₂| + ……+ |U - U_n| + |V - V_n|) 】

　　这样，就转换为求函数 y = |x - x1| +  |x - x2| +  |x - x3| + ……+ |x - xn|的最小值的问题，也许有人会问，公式(1 - 2)有两个变量U , V，而函数y只有一个变量x，其实很好办，就将公式(1 - 2)按照变量 U 和 V分为两部分，分别求最小值，和起来也肯定是最小值；

　　对于函数 y = |x - x1| +  |x - x2| +  |x - x3| + ……+ |x - xn| （x1 , x2, ……xn是从小到大排列）的最小值；可以用数学归纳法求解：

　　证明：假设n = 2,则 y = |x - x1| +  |x - x2|,假设 x₁ < x₂ ，当x ≤x₁ < x₂ 时，y = x1 + x2 - 2x , y_min = x2- x1; 当 x₁< x < x₂时，

y  = x2 - x1 ，则y_min = x2 - x1 ; 当 x ≥ x2 时，y = 2x - x1 - x2, y_min = x2 - x1；

　　若 n > 2 ，

　　当x < x1 < x2 <……< x_n 时，y = (x1 - x) + (x2 - x) +…… +(x_n - x) = (x1 + x2 + x3 +……+ x_n) - n * x;

　　当x1 < x < x2 <……< x_n 时，y =  (x1 + x2 + x3 + …… + x_n) - n * x + 2(x - x1);

　　当x1 < x2 < x <……< x_n 时，y =  (x1 + x2 + x3 + …… + x_n) - n * x + 2[(x - x1) + (x - x2)];

　　……

　　所以，当x1 < x2 < …x_k < x < x_k+1 <…< x_n 时，

　　y =  (x1 + x2 + x3 + …… + x_n) - n * x + 2[(x - x1) + (x - x2) + ……+ (x - x_k)]

　　　=  (x1 + x2 + x3 + …… + x_n)  +  2[ (k - n/2)x - (x1 + x2 + ……+  x_k) ]  --(1 - 4)

　　对于公式(1 - 4)，两边求导，可知当k - n/2 < 0 时，即k < n/2时，y 单调递增; 当k - n/2 > 0 时，即k > n/2时，y 单调递减;因为k= {1，2，3,……n},为整数，若 n 为偶数，则当 k = n/2 时，x = x_k, y 有最小值；若 n 为 奇数，则当 k = (n + 1)/2时，x = x_k, y 有最小值，证毕

　　综上所述，得到的最终结论是：当 n 为偶数时，y的最小值为y_min = (x_k+1 + x_k+2 + ……+x_n) - (x₁ + x₂ +……+ x_k) ， k = n/2 ;当 n 为奇数时，y的最小值为y_min = (x_k+1 + x_k+2 + ……+x_n) - (x₁ + x₂ +……+ x_{k - 1}) , k = (n + 1)/2 .

　　回到公式(1 - 2),分别求出(|U - U₁| + |U - U₂| + ……+ |U - U_n|) 和 (|V - V₁|  + |V - V₂| + ……+ |U - U_n| + |V - V_n|)的最小值，求平均数，即得到最小值bestDistance ，为程序所求.

来源：点击打开链接