序号 | 标题 | 作者 | 发表时间 | 费用 | 订购数 | 操作 |
---|
不同型号的无线电收发机有一个不同的参数d,两座村庄之间的距离如果不超过d就可以用该型号的无线电收发机直接通讯,d值越大的型号价格越贵。拥有卫星设备的两座村庄无论相距多远都可以直接通讯。
现在有k台(0 ≤k≤100)卫星设备,请你编一个程序,计算出应该如何分配这k台卫星设备,才能使所拥有的无线电收发机的d值最小,并保证每两座村庄之间都可以直接或间接地通讯。
A (10, 10) A B (10, 0) C (30, 0) B C 其中 | AB |= 10 | BC |= 20 | AC |= $10\sqrt5$ ≈22.36
如果没有任何卫星设备或只有 1 台卫星设备(k=0 或 k=1) ,则满足条件的 最小的 d = 20,因为 A 和 B,B 和 C 可以用无线电直接通讯;而 A 和 C 可以用 B 中转实现间接通讯(即消息从 A 传到 B,再从 B 传到 C) ;
如果有 2 台卫星设备(k=2) ,则可以把这两台设备分别分配给 B 和 C,这 样最小的 d 可取 10,因为 A 和 B 之间可以用无线电直接通讯;B 和 C 之间可以 用卫星直接通讯;A 和 C 可以用 B 中转实现间接通讯。
如果有 3 台卫星设备,则 A,B,C 两两之间都可以直接用卫星通讯,最小的 d 可取 0。