题目详情
要建立一个信号基站服务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 – 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 ,为程序所求.
来源:点击打开链接
分享到:
相关推荐
要建立一个信号基站服务n个村庄,这n个村庄用平面上的n个点表示。假设基站建立的位置在(X,Y),则它对某个村庄(x,y)的距离为max{|X – x|, |Y – y|}, 其中| |表示绝对值,我们的目标是让所有村庄到信号基站的距离和...
信号强度读取程序,可以定时往SQLite数据库里存储数据。经过U8500真机测试。
以基站信号作为雷达的信号源,对低小慢目标进行检测。
NiceTrack 源码,基站信号开发源码
WM手机上很好用的基站信号测试,希望大家会喜欢
移动基站联通基站全国基站数据库(基站查询)
基站测试MiniCell v1.0.0.9 是一款功能强大的基站信号监测器,可以显示手机的运营商、网络类型、LAC(位置区码)、CID(小区ID)、信号强度、相邻小区信息等基站信号相关信息是手机信号监测等专业人士或爱好者的必备...
网优基站培训资料,网优基站培训资料网优基站培训资料
基站站点参数表是基站工程参数表,基站本机在测试时应该对基站的站点参数表实施 采集与核对,确保各个参数的真实有效,以利于后期对基站的正常工作和基站维护、网 络优化予以基本保证。基站工程参数表主要有基站的...
基于模糊聚类分析的信号满意度基站选址研究,吴莹,马云峰,移动基站选址的合理性与用户对基站信号满意度有着密切关系。根据居民对移动基站电磁辐射满意度这一重要因素,从覆盖角度对选址问
在英特尔架构上进行LTE基站无线信号处理
通信网络由众多基站组成, 这些基站在初始建立完成后,督导将基站硬件和 传输数据做到基站 BBU 中去,通过基站告警排查, 使基站处于 on air 状态,那么 接下来就需要单验人员对该站点进行单站验证, 简称单验。 在...
基站是移动通信中组成蜂窝小区的基本单元,主要完成移动通信网和移动通信用户之间的通信和管理功能,从狭义上就可以把基站理解成一种无线电收发信电台。换句话说,你的手机信号从哪里来,手机能上网、打电话都是因为...
用于测试手机信号轻度 和位置 和类别 的一种然间
GIS通讯基站分布及信号强度分析项目效果图.part01可以用到方案里面忽悠客户的东西,该资源资源来自网络。
换句话说,你的手机信号从哪里来,手机能上网、打电话都是因为你的手机(专业术语称为终端UE)驻留在一个基站上,在基站信号的覆盖范围内。基站不是孤立存在的,它仅仅属于网络架构中的一部分,它是连接移动通信网和...
用户使用非法信号放大器造成基站底噪抬升:在CDMA网络中,基站侧RSSI异常,会严重影响接入性能、语音质量、接入保持状态、数据业务吞吐率等网络关键性能,导致用户感知度变差。本文为在底噪故障处理过程中,发现用户...
该测试软件主要适用于诺基亚手机,它是基站信号测试软件,大家可以试试,测试3G时是WCDMA的
1. 显示当前通讯基站的位置、方位角、信号强度、距离、邻区信息。 2. 离线地图为您节省流量。 3. 基于LAC-CI/ SID-NID-BID的查询并标注。 4. 趋近告警,导航功能。 5. 室外路测信号的记录和回放(Android 、PC均支持...