华为 OD 机试：最佳信号覆盖问题解析与多语言实现

最佳信号覆盖问题

在华为 OD 机试中，这类模拟类题目考察的是对距离计算和遍历策略的掌握。本题要求在一个二维坐标系中找到一个点，使得该点接收到的所有 AP（无线接入点）的信号强度之和最大。

题目核心逻辑

我们需要处理两个关键概念：切比雪夫距离和信号衰减模型。

1. 坐标与距离

题目规定使用切比雪夫距离（Chebyshev distance）。对于两个点 $(x_1, y_1)$ 和 $(x_2, y_2)$，其距离 $d$ 为： $$ d = \max(|x_1 - x_2|, |y_1 - y_2|) $$ 这意味着在以目标点为中心的方形区域内，只要横纵坐标差值的最大值不超过覆盖半径 $D$，AP 就能覆盖到该点。

2. 信号衰减规则

每个 AP 有初始信号强度 $s$。当距离为 $d$ 时，实际信号强度为向下取整后的值： $$ \text{signal} = \lfloor s / (1 + d) \rfloor $$ 如果 $d > D$，则该 AP 无法覆盖此点，贡献为 0。

3. 搜索范围

由于 $N$ 和 $D$ 都不超过 100，且坐标均为整数，我们不需要遍历整个无限平面。有效搜索区域可以限制在所有 AP 坐标的边界向外扩展 $D$ 的范围内。考虑到数据规模较小，直接遍历这个矩形区域内的所有整数坐标即可。

输入输出规范

输入描述： 第一行包含两个整数 $N$ 和 $D$（$N \le 100, D \le 100$），分别表示 AP 数量和最大覆盖距离。 接下来 $N$ 行，每行三个整数 $x, y, s$，表示 AP 的坐标 $(x, y)$ 及初始信号强度 $s$。

输出描述： 输出一个整数，代表能接收到的最大信号强度总和。

代码实现思路

解决这个问题的关键在于如何高效地确定搜索边界以及如何快速累加信号。我们可以先找出所有 AP 坐标的最小/最大横纵坐标，然后在这个基础上向四周各扩展 $D$ 个单位作为遍历的上下界。这样既保证了不漏掉最优解，又避免了无效的全局遍历。

下面给出 C++ 和 Python 的实现示例，重点展示如何计算距离和累加信号。

C++ 实现

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

struct AP {
    int x, y, s;
};

int main() {
    int N, D;
    if (!(cin >> N >> D)) return 0;

    vector<AP> aps(N);
     minX = , maxX = ;
     minY = , maxY = ;

    
     ( i = ; i < N; ++i) {
        cin >> aps[i].x >> aps[i].y >> aps[i].s;
        minX = (minX, aps[i].x);
        maxX = (maxX, aps[i].x);
        minY = (minY, aps[i].y);
        maxY = (maxY, aps[i].y);
    }

    
     start_x = (, minX - D);
     end_x = maxX + D;
     start_y = (, minY - D);
     end_y = maxY + D;

     max_signal = ;

    
     ( cx = start_x; cx <= end_x; ++cx) {
         ( cy = start_y; cy <= end_y; ++cy) {
             current_signal = ;
             ( & ap : aps) {
                
                 dist = ((cx - ap.x), (cy - ap.y));
                
                
                 (dist <= D) {
                    current_signal += ap.s / ( + dist);
                }
            }
            max_signal = (max_signal, current_signal);
        }
    }

    cout << max_signal << endl;
     ;
}