首页 > 试题广场 >

路由器

[编程题]路由器

热度指数：3444 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

一条直线上等距离放置了 n 台路由器。路由器自左向右从 1 到 n 编号。第 i 台路由器到第 j 台路由器的距离为 | i - j | 。每台路由器都有自己的信号强度，第 i 台路由器的信号强度为 a_i 。所有与第 i 台路由器距离不超过 a_i 的路由器可以收到第i台路由器的信号（注意，每台路由器都能收到自己的信号）。问一共有多少台路由器可以收到至少k台不同路由器的信号。

数据范围： $1 \le n,k \le 10^5 \$ ， $0 \le a_i \le 10^9 \$

输入描述:

输入第一行两个数n , k

第二行n个数, a1 , a2 , a3……… , an

输出描述:

输出一个数，一共有多少台路由器可以收到至少k台不同路由器的信号。

示例1

输入

4 4
3 3 3 3

输出

算法知识视频讲解

Python

想去夏威夷的莲雾许愿简历通过

n,k = list(map(int,input().split()))
num = list(map(int,input().split()))

list1 = [0] * (len(num)+1)
for i in range(n):
list1[max(0, i-num[i])] += 1
list1[min(i+num[i]+1, len(num))] -= 1
sum = 0
start = 0
for i in range(n):
start += list1[i]
if start>=k:
sum += 1

print(sum)

python通过查分数组实现路由器

编辑于 2022-03-26 12:38:40 回复(0)

Python

这题太难了

推荐一个差分数组的讲解，转载的哦。

https://blog.dotcpp.com/a/56355-5

发表于 2020-03-07 11:18:42 回复(0)

Python

白色纯度

这道题目和火车站台简直是一模一样，看不懂答案的可以先做火车站台这道题目：

https://www.nowcoder.com/practice/bade66d32ad8479fbcecc002ea983ff0?tpId=98&tqId=33040&tPage=8&rp=8&ru=/ta/2019test&qru=/ta/2019test/question-ranking

下面是python3的代码：

第一个for循环就是仿照火车站的起点和终点，终点不计算在内。剩余的两个for循环就是火车站台的代码，需要代码的可以点击python排行里面，看头像是个哈巴狗的用户代码。

if __name__=='__main__':
    n,k = list(map(int,input().split()))
    num = list(map(int,input().split()))
    res = []
    for i in range(n):
        l = max(0,i-num[i])
        r = min(n,i+num[i]+1)
        res.append((l,r))
    dp = [0 for _ in range(n+1)]
    for i in range(n):
        dp[res[i][0]] += 1
        dp[res[i][1]] -= 1
    count = 0
    temp = 0
    for i in range(len(dp)):
        temp += dp[i]
        if temp >= k:
            count += 1
    print(count)

发表于 2019-08-11 16:13:20 回复(0)