首页 > 试题广场 >

路由器

[编程题]路由器

热度指数：3464 时间限制：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

输出

算法知识视频讲解

Java

间客.

首先得明白差分数组的概念。
差分数组：对于数组[a1,a2,a3,a4...],其查分数组[a1,a2-a1,a3-a2,a4-a3...]。第i项的值等于查分数组前i项的和。

这个概念有什么用呢？加入我们需要在[i,j)范围内都进行+1操作，对于原数组，可以遍历第i到j项都进行+1，但这样时间复杂度有点大。
如果用了差分数组，就可以在第i项+1，第j+1项-1就行了。只需操作两个地方。

对于这题，某一个路由器ax，其辐射的范围从i到j，我们如果遍历每个x，再从对应的i到j都+1操作，时间复杂度太大。那么就可以用差分数组。
用一个数组dp[]表示第i个路由器能接受到多少个信号,都是从0开始,遍历路由器数组arr[],计算出每一个路由器辐射的范围,start到end,然后对差分数组进行dp[start]++,dp[end+1]--操作,即表示对结果数组从start到end进行+1操作.
最后,累加遍历dp数组,就能得到每一个路由器能接收的到信号数.

发表于 2020-06-07 14:42:02 回复(0)

Java

taihelsetw

这题思路挺巧妙的，常规思路就是用一个数组记录每个路由器能接收到的路由器信号的个数，先找出每个路由器能够覆盖的范围[left,right)，然后对于范围内的数组元素加一，这样复杂度太高了。换一个思路，对于每一组left和right，我们用一个数组count使count[left] += 1,count[right] += -1,然后对count从左向右累加，例如某个路由器覆盖[0,4)这个范围，我们令count[0] = 1,count[-1] = -1，这样累加后得到{1，1，1，1，0，...};我们对每组都做这样的处理就ok了。

import java.util.Scanner;
public class Main{
public static void main(String args[]){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), k = sc.nextInt(), ai = 0;
int bound[][] = new int[n][2];
int[] count = new int[n];
for(int i = 0; i < n; i++){
ai = sc.nextInt();
bound[i][0] = i-ai>0?i-ai:0;
bound[i][1] = i+ai<n-1?i+ai+1:n;
count[bound[i][0]] += 1;
if(bound[i][1] < n)
count[bound[i][1]] += -1;
}
int result = 0;
for(int i = 0; i < n; i++){
if(i-1>=0) count[i] += count[i-1];
if(count[i] >=k) result++;
}
System.out.println(result);
}
}

编辑于 2019-09-19 21:09:48 回复(0)