路由器_美团笔试题

芥末篮子

首先介绍差分数组

给定原数组 a = {a₁, a₂ , a₃ , a₄ , a₅ }，

对应差分数组 b= {a₁, a₂-a₁_,a₃-a₂, a₄-a₃, a₅-a₄, -a₅}

即，差分数组为原数组每一项与前一项的差，原数组为差分数组的前n项和(S_n)

对于本题，暴力解法是用一个数组，存储每一个路由器能收到的信号数，复杂度为O(n²)

考虑到对路由器a，它能发送的最左路由器b会比b左侧的路由器多收到一条信号（来自a）；

它右侧发送不到的第一个路由器c会比c左侧的路由器少收到一条信号（来自a）

因此我们对每个路由器，用它作为b的次数减去作为c的次数，就能得到它比前一台路由器多收到几条信号，就能获得差分数组，从而还原出原数组

实现代码如下：

#include<iostream>
(720)#include<stdio.h>
#define MaxN 100010

using namespace std;

int N, K;
int chafen[MaxN];//差分数组

int main(){
    scanf("%d%d", &N, &K);
    int temp;
    for(int i=0; i<N; i++){
        scanf("%d", &temp);
        chafen[max(0, i-temp)]++;   //最左发送范围
        chafen[min(N, i+temp+1)]--;  //最右发送范围的下一个路由器
    }
    int sum = 0, ans = 0;
    for(int i=0; i<N; i++){
        sum+=chafen[i];         //还原出原数组第i项
        if(sum >= K)
            ans++;
    }
    cout<<ans<<endl;
    return 0;
}

发表于 2020-04-09 17:17:20 回复(0)

简单点说话方式简单点

看了这么多题解，根本没看懂，说一下我个人对这道题的理解。

首先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)

上面主要使用了两个存储:
res 和 dp
res 的作用是记录每个路由器能到达的左边界。
res[i][0] = 0的话，表示路由器i最左边能到达坐标 0 。
也说明了能到达坐标 1, 2, ... 。但是最右能到达哪呢？这个在res[i][1] 记录着。

dp数组累加表示坐标 i 有几个路由器能到达。
看下面dp怎么算的，大家就能理解这个算法奥秘了。

for i in range(n):
        dp[res[i][0]] += 1
        dp[res[i][1]] -= 1

以
4 4
3 1 3 2 为例。
我把它的res dp 结果输出了。
('res = ', [(0, 4), (0, 3), (0, 4), (1, 4)])
('dp = ', [3, 1, 0, -1, -3])

这个方法还是很巧妙，有知道这种题是属于什么类型的，求告知，感谢！！！

发表于 2019-08-21 18:48:01 回复(2)

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)

练习时长两年半的Java练习生

public class Main {
    public static void main(String[] args) {
        java.util.Scanner sc = new java.util.Scanner(System.in);
        int N = sc.nextInt(), K = sc.nextInt();
        int[] delta = new int[N + 2];
        for (int i = 1; i <= N; ++i) {
            int r = sc.nextInt();
            delta[Math.max(0, i - r)] += 1;
            delta[Math.min(N + 1, i + r + 1)] -= 1;
        }
        int cnt = 0, sum = delta[0];
        for (int i = 1; i <= N; ++i) {
            sum += delta[i];
            if (sum >= K) {
                ++cnt;
            }
        }
        System.out.println(cnt);
    }
}

发表于 2019-06-29 21:11:21 回复(0)

overflowing

恕我直言，没一个答案把此题的思路讲清楚，代码我就不贴了，大同小异。此题的的求解关键在于差分数组，不是什么dp。看不懂代码的同学强烈建议搜索差分数组，理解其原理性质后再读代码就很好理解了。

发表于 2020-03-05 11:14:57 回复(0)

pein531

差分数组：

设原数组 a = {a1, a2 , a3 , a4 , a5 }，

差分数组 b = {a1, a2-a1, a3-a2, a4-a3, a5-a4, -a5}

原数组中的ai即为差分数组中前i项的和

n, k = map(int, input().strip().split())
route = list(map(int, input().strip().split()))
area = []
# 计算路由i的信号能到达的左右边界
for i in range(n):
    left = max(0, i - route[i])           # 路由i能到达的左边界
    right = min(n, i + route[i] + 1)      # 路由i能到达的右边界(第一个到达不了的路由)
    area.append((left, right))
"""
对于路由器i，它能发送的最左路由器b会比b左侧的路由器多收到一条来自i的信号；
它右侧发送不到的第一个路由器c会比c左侧的路由器少收到一条来自i的信号。
"""
diff = [0]*(n + 1)
for i in range(n):
    # 对于路由器i，用其作为左边界的次数-作为右边界的次数，就可以得到它比前一台路由多收到几条信号，即差分
    diff[area[i][0]] += 1
    diff[area[i][1]] -= 1
# 利用差分数组的前i项和就可以还原出原数组的第i项
count = 0
counter_i = 0
for i in range(n + 1):
    counter_i += diff[i]
    if counter_i >= k:
        count += 1
print(count)

发表于 2021-02-02 17:03:16 回复(0)

C/C++

DearStranger

#include <iostream>
(720)#include <bits/stdc++.h>
using namespace std;
//学习到了查分数组，进行复杂度为o（n）的遍历
int coverage(vector<int> num,int k)
{
    int n=num.size();
    vector<int> dp(n,0);
    for(int i=0;i<n;i++)
    {
        dp[max(0,i-num[i])]+=1;
        if(i+num[i]+1<n) dp[i+num[i]+1]-=1;
    }
    int res=0;
    int cover=0;
    for(int i=0;i<n;i++)
    {
        cover+=dp[i];
        if(cover>=k) res++;
    }
    return res;
}
int main()
{
    int N,k;
    while(cin>>N>>k)
    {
        vector<int> strength(N,0);
        for(int i=0;i<N;i++)
        {
            cin>>strength[i];
        }
        cout<<coverage(strength,k);
    }
}

发表于 2020-04-02 13:34:33 回复(0)

C/C++

nbgao

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n,k;
    cin>>n>>k;
    int a[n+1],c[n+1];
    memset(c,0,sizeof(c));
    for(int i=1;i<=n;i++){
        cin>>a[i];
        c[max(0,i-a[i])]++;
        c[min(n+1,i+a[i]+1)]--;
    }
    int cnt=0,t=c[0];
    for(int i=1;i<=n;i++){
        t += c[i];
        if(t>=k)
            cnt++;
    }
    cout<<cnt<<endl;
    return 0;
}

发表于 2019-09-29 12:55:00 回复(0)

花泽类的泪

package main

import "fmt"

func main() {
	var n, k, a int
	ans, count := 0, 0
	fmt.Scan(&n)
	arr := make([]int, n+1)
	fmt.Scan(&k)
	for i := 0; i < n; i++ {
		fmt.Scan(&a)
		arr[max(0, i-a)]++
		arr[min(n, i+a+1)]--
	}
	for i := 0; i < n; i++ {
		count += arr[i]
		if count > k {
			ans++
		}
	}
	fmt.Println(ans)
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

发表于 2022-08-04 16:44:52 回复(0)

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)

╭(′•o•′)╭☞就是这个人！

import java.io.*;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws IOException{
        Scanner in = new Scanner(System.in);
        int n= in.nextInt();
        int k = in.nextInt();
        int []temp=new int[n+2];
        int ans=0;
        for(int i=1;i<=n;i++){
            int r=in.nextInt();
            temp[Math.min(n+1,i+r+1)]-=1;
            temp[Math.max(0,i-r)]+=1;
        }
        int res=0;
        ans=temp[0];
        for(int i=1;i<=n;i++){
            ans+=temp[i];
            if(ans>=k)res++;
        }
        System.out.println(res);
    }
}

差分数组主要用于快速的在一个区间内同时加减一个数ans

思想体现在与区间同时变，而其间的差值不变，所以只要更新首末位置即可，区间左端点位置的值+ans，（右端点+1）位置的值-ans。

发表于 2021-05-15 00:22:39 回复(0)

牛客763745392号

import java.util.*;


public class Main
{
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);
        
        int n ,k;
        n = sc.nextInt();
        k = sc.nextInt();
        
        // 构造差分数组
        int[] router = new int[n + 5];
        
        int ans = 0;
        for(int i = 1; i <= n; i++)
        {
            int sig = sc.nextInt();
            for(int j = sig; j >= 0; j--)
            {
                if(i - j >=1)
                {
                    router[i-j] += 1;
                    break;
                }
            }
            
            for(int j = sig; j >=0; j--)
            {
                if(i + j + 1 <= n + 2)
                {
                    router[i+j+1] -= 1;
                    break;
                }
            }
        }
        
        int init = 0;
        for(int i = 1 ; i <= n; i++)
        {
            init += router[i];
            if(init >= k)
                ans += 1;
            //System.out.println(init);
        }
        
        System.out.println(ans);
    }
}

发表于 2021-03-18 13:50:11 回复(0)

kangjinci

//差分
#include<iostream>

using namespace std;
const int N = 1e5 + 5;
int a[N];
int diff[N];
int n, k;


int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    //i - j <= a[i]
    for (int i = 1; i <= n; i++) {
        diff[max(1, i - a[i])]++;
        diff[min(n + 1, i + a[i] + 1)]--;
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        diff[i] += diff[i - 1];
        if (diff[i] >= k) {
            ans++;
        }
    }
    cout << ans << endl;

    return 0;
}

发表于 2021-03-10 19:00:02 回复(0)

simbayx

#include<iostream>
#include<vector>
#include<string>
using namespace std;
int main(){
    int n,k,temp,cover=0;
    int l=0;
    cin>>n>>k;
    vector<int> sum(n,0);
    for(int i=0;i<n;i++){
        cin>>l;
        if(l>=i) sum[0]++;
        else sum[i-l]++;
        if(l+i+1<n) sum[l+i+1]--;
    }
    for(int i=1;i<=n;i++){
        cover+=sum[i-1];
        if(cover>=k) temp++;
    }
    cout<<temp;
    return 0;
}

发表于 2020-09-02 01:15:23 回复(0)

Allen没有青春

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();
        int k=scanner.nextInt();
        int[] a=new int[n+1];
        int[] countl=new int[n+1];
        int[] countr=new int[n+1];
        for(int i=1;i<=n;i++){
            a[i]=scanner.nextInt();
        }
        for(int i=2;i<=n;i++){
            if(Math.abs(i-1)<=a[i]) {//1号收到来自右边的信号
                countr[1]+=1;
            }
        }
        for(int i=2;i<=n;i++){
            countr[i]=countr[i-1];//i接受右边到的信号数量应该等于i-1接收到的数量
            if(a[i]>=1) countr[i]-=1;//如果i给i-1提供了信号，那么i右边信号量-1
        }

//        for(int i=1;i<=n;i++) System.out.print(countl[i]);
//        System.out.println();

        for(int i=n-1;i>=0;i--){
            if(Math.abs(i-n)<=a[i]) {//n号收到来自左边的信号
                countl[n]+=1;
            }
        }
        for(int i=n-1;i>=0;i--){
            countl[i]=countl[i+1];
            if(a[i]>=1) countl[i]-=1;
        }

//        for(int i=1;i<=n;i++) System.out.print(countr[i]);
//        System.out.println();

        int ans=0;
        for(int i=1;i<=n;i++)
            if((countl[i]+countr[i]+1)>=k) ans++;
        System.out.println(ans);

    }

}

这样只通过了1/3，为什么呢？

发表于 2020-07-30 15:56:44 回复(0)

美团内推（专业正版）

#include<iostream>
#include<vector>
using namespace std;

int main()
{
    int n, k;
    cin >> n >> k;
    
    vector<int>distances(n);
    for(int i = 0; i < n; i++)
    {
        cin >> distances[i];
    }
    vector<int>chafen_counts(n, 0);
    for(int i = 0; i < n; i++)
    {
        if(i - distances[i] > 0)
        {
            chafen_counts[i - distances[i]] += 1;
        }
        else
        {
            chafen_counts[0] += 1;
        }
        
        if(i + distances[i] + 1 <= n-1)
        {
            chafen_counts[i + distances[i] + 1] -= 1;
        }
        
    }
    
    for(int i = 0; i < n; i++)
    {
        if(i > 0)
        {
            chafen_counts[i] += chafen_counts[i - 1];
        }
    }
    
    int number = 0;
    for(int i = 0; i < n; i++)
    {
        if(chafen_counts[i] >= k)
        {
            number++;
        }
    }
    cout << number;
    return 0;
}

首先得明白差分数组的概念。
差分数组：对于数组[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-07-02 17:19:40 回复(0)

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)

tangmy326

和火车进站那题一个思路

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

发表于 2020-06-06 10:47:39 回复(0)

牛客830378771号

提供一个不一样的思路：优先队列，复杂度O(n)

// 对于路由器i，它能收到信号的路由器可以分为左侧的、自己、右侧的：counter[i] = 被左侧信号覆盖 + 1 + 被右侧信号覆盖
// 被左侧信号覆盖，可以用最小优先队列实现；同理，被右侧信号覆盖，可以用最大优先队列实现。
#include<iostream>
#include<vector>
#include<queue>
 
using namespace std;
 
 
int solution(vector<int> &A, int k) {
    if (A.size()<k || A.empty()) return 0;
    priority_queue<int, vector<int>, greater<int>> q_l;
    priority_queue<int> q_r;
    vector<int> counter(A.size());
    for (int i=0; i<A.size(); ++i) {
        while (!q_l.empty() && q_l.top()<i) q_l.pop();
        counter[i] += q_l.size();
        q_l.push(i+A[i]);
    }
    for (int i=A.size()-1; i>=0; --i) {
        while (!q_r.empty() && q_r.top()>i) q_r.pop();
        counter[i] += q_r.size();
        q_r.push(i-A[i]);
    }
    int res=0;
    for (int i=0; i<A.size(); ++i) {
        if (counter[i]>=k-1) ++res;
    }
    return res;
}
 
 
int main(int argc, char **argv) {
    ios::sync_with_stdio(false);
    int n, k;
    if (cin >> n >> k) {
        vector<int> A(n);
        for (int i=0; i<n; ++i) cin >> A[i];
        cout << solution(A, k) << endl;
    }
    return 0;
}

编辑于 2020-05-02 14:30:00 回复(0)

张小酸

我在eclipse跑出来了，在这里提交报数组越界，哪位大哥知道咋回事

发表于 2020-04-22 09:26:56 回复(0)

路由器

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题