庞果网之建立信号基站

曾经终败给现在 2022-05-13 00:04 131阅读 0赞

题目详情

要建立一个信号基站服务n个村庄，这n个村庄用平面上的n个点表示。假设基站建立的位置在(X,Y)，则它对某个村庄(x,y)的距离为max\{|X – x|, |Y – y|\}， 其中| |表示绝对值，我们的目标是让所有村庄到信号基站的距离和最小。

基站可以建立在任何实数坐标位置上，也可以与某村庄重合。

**输入**：

给定每个村庄的位置x\[\],y\[\]，x,y都是整数，满足：

\-1000000000 < x,y < 1000000000

村庄个数大于1，小于101。

**输出**：

所有村庄到信号基站的距离和的最小值。

关于精度：

因为输出是double。我们这样判断对错，如果标准答案是A,你的答案是a，如果|Ａ – a| < 1e-3 我们认为是正确的，否则认为是错误的。

**样例**：

假设有4个村庄位置分别为 （1，4） （2，3） （0，1） （1，1）

我们的结果是5。因为我们可以选择（1.5，2.5）来建立信号基站。

bestDistance = max(|1.5-1|, |2.5-4|) + max(|1.5-2|,|2.5-3|) + max(|1.5-0|,|2.5-1|) + max(|1.5-1|,|2.5-1|)

= max(0.5, 1.5) + max(0.5,0.5) + max(1.5,1.5) + max(0.5,1.5)

= 1.5 + 0.5 + 1.5 + 1.5

= 5

/*********************************
    *   日期：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 – y1|\} =（|X+Y-x1\-y1|+|X-Y-(x1\-y1)|）/2, ……，（|X+Y-xn\-yn|+|X-Y-(xn\-yn)|）/2;也就是最短距离

bestDistance = 1/2 \*（|X+Y-(x1\+y1)| + |X-Y-(x1\-y1)| +|X+Y-(x2+y2)| + |X-Y-(x2\-y2)| +……+ |X+Y-(xn\+yn)|+|X-Y-(xn\-yn)|） --**(1-1)**

其中，x1\+y1 、x1\-y1 、x2+y2 、x2\-y2 、……、xn\+yn 、xn\-yn均为常数, 通过题目所给的数组可以容易得到这些值

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

bestDistance =1/2 \*(|U - U1| +|V - V1| +|U - U2| +|V - V2| + ……+|U - Un| +|V - Vn|) --**(1 - 2)**

**　　　　　=**1/2 \*【(|U - U1| +|U - U2|+ ……+|U - Un|)+ (|V - V1| +|V - V2| + ……+|U - Un| +|V - Vn|) 】

这样，就转换为求函数**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|,假设x1<x2，当x ≤x1<x2时，y = x1 + x2 - 2x , ymin= x2- x1; 当x1<x<x2时，

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

若 n >2 ，

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

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

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

……

所以，当x1<x2 < …xk< x < xk+1<…< xn时，

y =(x1 + x2 + x3 + …… + xn) - n \* x + 2\[(x - x1) + (x - x2) + ……+ (x - xk)\]

= (x1 + x2 + x3 + …… + xn) + 2\[ (k - n/2)x - (x1 + x2 + ……+ xk) \] --**(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 = xk,**y**有最小值；若**n**为奇数，则当 k = (n + 1)/2时，x = xk,**y**有最小值，证毕

**综上所述，得到的最终结论是：当 n 为偶数时，y的最小值为ymin= (xk+1\+xk+2\+ ……+xn) - (x1\+x2\+……+xk) ， k = n/2 ;当 n 为奇数时，y的最小值为ymin= (xk+1\+xk+2\+ ……+xn) - (x1\+x2\+……+xk - 1) , k = (n + 1)/2 .**

回到公式(1 - 2),分别求出(|U - U1|+|U - U2|+ ……+|U - Un|) 和(|V - V1| +|V - V2| + ……+|U - Un| +|V - Vn|)的最小值，求平均数，即得到最小值bestDistance ，为程序所求.

来源：[点击打开链接][Link 1]

天猫搞活动。。。。。。。。

我在用来往，用它我们就能免费语聊！11月1日到11月9日用淘宝账号登陆我还能送你2元双11现金红包！我在来往上叫sjf0115，搜索下sjf0115来找我聊天吧！点击 [点击打开链接][Link 2],赶紧拿红包吧！

[Link 1]: http://www.cnblogs.com/bestDavid/p/stationInfo.html
[Link 2]: http://lwurl.to/1jOgJ