shunfurh
编程介的小学生
2019-06-17 20:56
采纳率: 92.7%
浏览 207

C语言优化方案计算,使得n个传感器连通,并且所有传感器的Inference之和最小,怎么实现的呢

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

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

Output
对于每组数据,输出一行包含一个整数,表示最小可能的Inference之和。

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

Sample Output
4
8
13

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

相关推荐