刷题笔记合集🔗

信号发射和接收

问题描述

有一个二维的天线矩阵，每根天线可以向其他天线发射信号，也能接收其他天线的信号，为了简化起见，我们约定每根天线只能向东和向南发射信号，换言之，每根天线只能接收东向或南向的信号。

每根天线有自己的高度 ，每根天线的高度存储在一个二维数组中，各个天线的位置用 表示， 代表天线的行位置（从 开始编号）， 代表天线的列位置（从 开始编号）。

在某一方向（东向或南向），某根天线可以收到多根其他天线的信号（也可能收不到任何其他天线的信号），对任一天线 X 和天线 Y，天线 X 能接收到天线 Y 的条件是：

1. 天线 X 在天线 Y 的东边或南边
2. 天线 X 和天线 Y 之间的其他天线的高度都低于天线 X 和天线 Y，或天线 X 和天线 Y 之间无其他天线，即无遮挡。

给一个 行 列的矩阵（二维数组），矩阵存储各根天线的高度，求出每根天线可以接收到多少根其他天线的信号，结果输出到 行 列的矩阵（二维矩阵）中。

输入格式

输入为 个 行 列的矩阵（二维矩阵），矩阵存储各根天线的高度，高度值 为大于 的整数。

第一行为输入矩阵的行数和列数，如：

第二行为输入矩阵的元素值，按行输入，如：

... ... ... ...

输出格式

输出一个 行 列的矩阵（二维数组），矩阵存储每根天线能收到多少根其他天线的信号，根数为 。

第一行为输出矩阵的行数和列数，如:

第二行为输出矩阵的元素值，按行输出，如：

... ... ... ...

样例输入

1 6
2 4 1 5 3 3

2 6
2 5 4 3 2 8 9 7 5 10 10 3

样例输出

1 6
0 1 1 2 1 1

2 6
0 1 1 1 1 4 1 2 2 4 2 2

数据范围

题解

这道题目主要考察的是如何处理天线信号的发射和接收问题。根据题目描述，我们需要计算每个天线可以接收到多少其他天线的信号。

首先分析一下题目条件：

1. 天线只能向东（右）和向南（下）发射信号
2. 天线接收信号的条件是：位于发射天线的东边或南边，且中间没有高度大于等于发射天线或接收天线的其他天线阻挡

如果用暴力方法，我们需要对每个天线作为接收点，向西（左）和向北（上）搜索所有可能发射信号的天线，这样的时间复杂度将达到 O(m²n² + mn²)，显然无法在给定的数据范围内高效执行。

一个更优的解法是使用单调栈。我们可以分别处理每行（东西方向）和每列（南北方向）：

1. 对于每行，我们从左到右遍历，使用一个单调递减栈记录可能的发射天线
2. 对于每列，我们从上到下遍历，同样使用单调递减栈记录可能的发射天线

单调栈的工作原理如下：

• 当前天线可以接收到栈中所有比它矮的天线的信号（因为这些天线之间没有更高的天线阻挡）
• 当前天线也可以接收到和它等高的天线的信号
• 当前天线无法接收到比它高的天线的信号（因为会被阻挡）

具体算法步骤：

1. 初始化结果矩阵ret，所有元素为0
2. 对每一行进行处理：
   • 创建一个空的单调递减栈
   • 从左到右遍历当前行的每个天线
   • 如果栈不为空且当前天线高度大于栈顶天线高度，则当前天线可以接收到栈顶天线的信号，ret值加1，然后弹出栈顶继续比较
   • 如果栈不为空且当前天线高度等于栈顶天线高度，则当前天线可以接收到栈顶天线的信号，ret值加1，弹出栈顶
   • 如果栈不为空且当前天线高度小于栈顶天线高度，则当前天线可以接收到栈顶天线的信号，ret值加1
   • 将当前天线入栈
3. 对每一列进行类似的处理
4. 返回计算结果

这种方法的时间复杂度为O(mn)，非常高效。

举个具体例子，以样例1中的[2 4 1 5 3 3]来说明：

• 对于位置0（高度2）：栈为空，入栈，结果为0
• 对于位置1（高度4）：栈顶为2，4>2，位置1可接收位置0的信号，结果为1，将4入栈
• 对于位置2（高度1）：栈顶为4，1<4，位置2可接收位置1的信号，结果为1，将1入栈
• 对于位置3（高度5）：栈顶为1，5>1，位置3可接收位置2的信号；弹出1后栈顶为4，5>4，位置3还可接收位置1的信号，总计接收2个信号，将5入栈
• 对于位置4（高度3）：栈顶为5，3<5，位置4可接收位置3的信号，结果为1，将3入栈
• 对于位置5（高度3）：栈顶为3，3=3，位置5可接收位置4的信号，结果为1，将3入栈

该样例只有一行，所以不需要处理南北方向。最终结果为[0,1,1,2,1,1]，与期望输出一致。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

# 读取输入
m, n = map(int, input().split())
heights = list(map(int, input().split()))

# 构建天线矩阵
anth = []
for i in range(m):
    anth.append(heights[i*n:(i+1)*n])

# 初始化结果矩阵
ret = [[0 for _ in range(n)] for _ in range(m)]

# 处理每一行（东西方向）
def process_horizontal():
    for i in range(m):
        stack = []
        for j in range(n):
            # 当栈不为空且当前天线高于栈顶天线，可以接收到栈顶天线的信号
            while stack and anth[i][j] > stack[-1]:
                ret[i][j] += 1
                stack.pop()
            
            # 处理栈不为空的情况
            if stack:
                if anth[i][j] == stack[-1]:
                    # 当前天线高度等于栈顶，可以接收信号，但弹出栈顶（维护递减性）
                    ret[i][j] += 1
                    stack.pop()
                else:
                    # 当前天线高度小于栈顶，只能接收栈顶信号
                    ret[i][j] += 1
            
            # 将当前天线入栈
            stack.append(anth[i][j])

# 处理每一列（南北方向）
def process_vertical():
    for j in range(n):
        stack = []
        for i in range(m):
            # 当栈不为空且当前天线高于栈顶天线，可以接收到栈顶天线的信号
            while stack and anth[i][j] > stack[-1]:
                ret[i][j] += 1
                stack.pop()
            
            # 处理栈不为空的情况
            if stack:
                if anth[i][j] == stack[-1]:
                    # 当前天线高度等于栈顶，可以接收信号，但弹出栈顶（维护递减性）
                    ret[i][j] += 1
                    stack.pop()
                else:
                    # 当前天线高度小于栈顶，只能接收栈顶信号
                    ret[i][j] += 1