2 drizzlex DrizzleX 于 2015.06.15 16:01 提问

如何用多个传感器访问一条线上的多个点?

如下问题:

对于一条线上的n个点,m个传感器。如何分配这些传感器,使得每个点都被一个传感器访问,并且使得所有传感器走过路径的最大值最小?

以下图为例:

图片说明

橙色长方形为传感器,蓝色的点为需要经过的目标,数字为这些点的坐标。每个传感器走过的路程长度为3(1-4), 3(5-8),和0(10000-10000)。传感器均从左往右运动。上例为最优分配,如果把传感器放在任意其他点上,则总会有一个传感器走过的路程大于3。

如何解决这个问题?

1个回答

smils
smils   2015.06.16 12:54

假设n=m ,
那么每个点 上都有一个传感器。,
假设n=m+1;
S =两个传感器之间的距离+右端点传感器的路径
1. 求出 最小的 S
2. 左端点传感器的路径 = S
3. 删除右端点传感器
4. 所有传感器走过的路径的最大值 = S
假设n=m+x;
重复 步骤 1-4 x次;
恳请指教

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
最多有多少个点在一条直线上-LintCode
给出二维平面上的n个点,求最多有多少点在同一条直线上。 样例: 给出4个点:(1, 2), (3, 6), (0, 0), (1, 3)。 一条直线上的点最多有3个。 思想: 利用map#ifndef C186_H #define C186_H #include<iostream> #include<vector> #include<cmath> #include<map> using n
这些点,有的近似在一条直线上,有的近似在另一条直线上,有的不在直线上,如何找出近似在一条直线上的点,并求出直线方程?
http://bbs.csdn.net/topics/320049780
判断几个点是否在同一条直线上(计算几何)
这里就要介绍一个概念:直线方程 直线方程 从平面解析几何的角度来看,平面上的直线就是由平面直角坐标系中的一个二元一次方程所表示的图形。求两条直线的交点,只需把这两个二元一次方程联立求解,当这个联立方程组无解时,两直线平行;有无穷多解时,两直线重合;只有一解时,两直线相交于一点。常用直线向上方向与 X 轴正向的 夹角( 叫直线的倾斜角 )或该角的正切(称直线的斜率)来表示平面上直线(对于...
使用单一 I²C 总线组合多个接近传感器---凯利讯半导体
近年来,接近传感器越来越备受关注。 例如,接近传感器现今广泛用于智能手机,在手机进行通话时停用触摸屏模式,因为此项功能可在用户视线离开屏幕时禁用触摸灵敏度,从而降低手机功耗。 此外,接近传感器还可最大限度地减少因用户身体部位碰触手机,而导致通话意外断开的风险。 直到最近,接近传感器仍是由发射 IR 光脉冲的红外 LED 和测量目标物反射光振幅的红外检测器组成。 这项技术使主机处理器能够估算传感器与
怎么用matlab标记曲线上符合条件的点
由一组n*2的数据画出一条曲线,然后在这条曲线上标记(以Y轴为例)大于或者小于某一个值的第一个点。 Example: 假设这两组数据是 Y -0.2057 -0.1291 -0.0588 0.0057 0.0646 0.1185 0.1678 0.2132 0.2545 0.2924 0.3269 0.3585 0.3873 0.413
OpenJudge百炼习题解答(C++)--题4072:判断多个点是否在同一直线
题: 总时间限制: 1000ms 内存限制: 65536kB 描述 有N(1个互不重合的点,并给出它们的坐标(xi,yi),问这些点是否在同一直线上。 输入第一行是测试的组数T(1 输出有T行,每行对应输入的一组数据,如果该组数据中的点在同一直线上,则该行输出True,否则输出False。 样例输入 1 3 0 0 2 2 1 1 样例输出 Tr
LintCode 最多有多少个点在一条直线上
题目给出二维平面上的n个点,求最多有多少点在同一条直线上。 样例给出4个点:(1, 2), (3, 6), (0, 0), (1, 3)。 一条直线上的点最多有3个。 解决思路 重复的点没有必要去增加时间复杂度, 先把point点简化成没有重复的新数组norepeatvalues以及记录每个新数组的成员point对应的重复次数repeatcounts数组; 两个点可以确定一条直线,假设有一个起始点P
判断几个点是否在一条直线上(计算几何)
链接:http://www.luogu.org/problem/show?pid=1142 题意:n个点,横坐标+纵坐标。判断最多有多少个点能再一条直线上(n 解析:求任意两个点构成的直线的方程 化为一般式:ax+by+c=0 得: a=y2-y1 b=x1-x2//注意别写反了 c=-ax1+by1 即可 不可思议的n = 700时n ^3也能过 #include
如何绘制一条连接两个点的曲线
本算法转载自如何制作一个类似Tiny Wings的游戏 Cocos2d-x 2.1.4 void drawCurves(CCPoint p0, CCPoint p1, void (*drawFunc)(CCPoint, CCPoint)) { #define kSegmentWidth 8 int segment = floorf((p1.x - p0.x) / kSegmentWidth
计算机图形学—判断点在直线上的方法
做计算机图形学实验的时候,要捕获和拖动直线或者是图形的某一条边。我们在寝室讨论如何判断鼠标在直线上的时候我的想法是扫描直线上的点再进行近似判断,在线上点附近就算是捕获直线了。有个同学想到了用三角形两边之和大于第三的原理。第二天我就急忙实现了。 算法的思想是:  已知三角形两边之和大于第三边,当鼠标点在直线上时点到直线两端点的距离和等于直线的长度,我们可以用点到两顶点