閱讀526 返回首頁    go 阿裏雲 go 技術社區[雲棲]

龐果網之建立信號基站

題目詳情

要建立一個信號基站服務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
*   題號: 題目 建立信號基站
*   來源：https://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 ，為程序所求.

來源：點擊打開鏈接




最後更新：2017-04-03 14:54:04

  上一篇：go 計算機體係結構3_單處理器內存訪問順序
  下一篇：go android解決同一個界麵上ScrollView和百度地圖（ListView等可滾動控件）滾動衝突問題