首页 > ACM题库 > HDU-杭电 > hdu 3707 Sensor待解决[解题报告]C++
2015
02-21

hdu 3707 Sensor待解决[解题报告]C++

Sensor

问题描述 :

在一条直线上有n个传感器,已知每个传感器的位置。现需要在这些传感器之间建立一些一对一连接。这些一对一连接是互不相同的,即同一传感器若与多个传感器建立连接,则需要建立多个一对一连接。
传感器A的传输半径定义为,与传感器A建立连接的所有传感器到A的最远距离,也就是传感器A需要多大的功率能够到达所有建立连接的传感器。
对于两个不同的传感器A和B,我们定义传感器A影响传感器B,当且仅当A和B之间的距离不超过A的传输半径。注意,A影响B并不意味着B一定影响A,因为传感器A和传感器B的半径可能是不同的。被传感器A影响的传感器数量称为传感器A的Inference。
现在请你计算一种连接方案,使得n个传感器连通,并且所有传感器的Inference之和最小。

输入:

输入包含多组数据,每组数据包含两行,第一行包含一个整数n (1 <= n <= 30),表示传感器的数目,第二行包含n个整数,表示每个传感器的坐标位置,坐标范围是[0,1000000000(10^9)]。
输入到文件结束为止

输出:

输入包含多组数据,每组数据包含两行,第一行包含一个整数n (1 <= n <= 30),表示传感器的数目,第二行包含n个整数,表示每个传感器的坐标位置,坐标范围是[0,1000000000(10^9)]。
输入到文件结束为止

样例输入:

3
1 3 7
5
3 4 2 5 1
6
1 2 4 8 16 32

样例输出:

4
8
13

Hint
假设我们把传感器根据输入顺序按照1, 2 …… n标号。 样例1:连接(1, 2) (2, 3) 样例2:连接(1, 2) (2, 4) (3, 1) (3, 5) 样例3:连接(1, 2) (2, 3) (2, 4) (4, 5) (4, 6)


  1. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

  2. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。