计算到达一组建筑物所需的最小路由器数量
计算到达一组建筑物所需的最小路由器数量
提问于 2022-09-28 00:14:53
我有range = n和numlist x= 2, 4 ,5,6,7,9,11,12和另一个numlist y= 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14，我想输出最少数量的路由器，以到达numlist x中的建筑物，以及我将它们放在哪一栋大楼上(我只会把它们放在numlist x的建筑物上)，前提是每个路由器都有n个范围。如果这里的范围是2，那么2号楼上的路由器只会到达建筑物2和4。如果我在楼6上有一个路由器，那么路由器将达到4,5,6,7,8楼等等。( numlist x中的建筑物才是重要的，numlist y只是作为参考)。到目前为止我有这个。
needed_towers = [2,4,5,6,7,9,11,12]
towers = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14] #only used here to get the intersect between the needed towers and towers so i can remove the unneeded numbers from the dictionary values
intersect = set(towers) - set(needed_tows)
r = 2
ans = []
placed = {}
a = [list(range(i-r,i + r + 1)) for i in needed_tows]
for i in a:
for j in intersect:
if j in i:
i.remove(j)
for i,x in zip(needed_tows,a):
placed[i] = x
#if needed_tows was [1,2,3,4,5] one of the solutions would be 2,5 or 2,4 and a few other solutions but i only need one.这个程序只是计算一个路由器会到达哪些建筑物，如果它被放置在每一个建筑物上，并将这些值放在字典中，下一步将是计算出我需要将它们放置在哪些建筑物上。从技术上讲，这个问题有很多解决方案，比如4,9,12甚至4,9,11，还有几个，但只要是最短的解决方案，就无所谓了。我如何编写一个程序来计算我必须在哪些建筑物上放置路由器，这样才能到达每一栋大楼？
回答 1
Stack Overflow用户
回答已采纳
发布于 2022-09-28 03:28:07
你可以试试这个：
from bisect import bisect
x = [2, 4, 5, 6, 7, 9, 11, 12]
r = 2
out = []
while x:
idx = -1 if (n := x[0] + r) > x[-1] else bisect(x, n) - 1
out.append(x[idx])
x = x[bisect(x, out[-1] + r):]
print(out)它规定：
[4, 9, 12]页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/73874983
复制相关文章
相似问题
腾讯云开发者
