首页 > 试题广场 >

路由器

[编程题]路由器

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

一条直线上等距离放置了 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

输出

算法知识视频讲解

17c89

发表于 2024-01-24 11:57:17

import java.util.Scanner; public class Main { public static void main(String[] args){ Scanner in = new Scanner(System.in); while 展开全文

laglangyue

发表于 2020-06-18 21:11:05

差分数组，差分数组就是找一个基准，D[i]=A[i]-A[i-1]表示第i个元素比前一个元素大D[i],那么从0到i的累加和就是D[i]比第0项大多少。如果使得第0项为0，然后在经过一系列变化，通过再与第0项对比就知道现在变化了多少，第0项在变化过程前后没有产生变化，因为它是基准。 ``` jav 展开全文