题解：B4242 [海淀区小学组 2025] 蜂窝网络

· · 题解

前言

夜深人静灯未熄， 键盘声声敲梦稀。 代码如诗行行密， bug似雾层层迷。

逻辑清晰心自定， 算法精妙意无羁。 千行万行终成器， 运行成功笑满衣。

屏幕微光映眼底， 程序世界任我驰。 不问窗外风雨急， 只因心中有晨曦。

题目理解

我们有 n 个城市和 m 个信号发射塔，它们都分布在一条直线上。每个信号发射塔可以覆盖其左右距离不超过 r 的城市。我们的任务是找到最小的 r，使得所有城市都被至少一个信号发射塔覆盖。

初步思路

  1. 问题分析：

    • 城市和信号发射塔的位置是给定的。
    • 我们需要找到一个最小的 r，使得每个城市都在至少一个信号发射塔的覆盖范围内。

  2. 关键点：

    • 对于每个城市，找到离它最近的信号发射塔。
    • 所有城市到最近信号发射塔的最大距离就是我们需要的最小 r。

算法选择

为了高效地找到每个城市到最近信号发射塔的距离，我们可以使用二分查找。具体来说：

  1. 排序：将城市和信号发射塔的位置分别排序。
  2. 二分查找：对于每个城市，使用二分查找在信号发射塔的位置中找到离它最近的信号发射塔。
  3. 计算距离：计算每个城市到最近信号发射塔的距离，并取最大值作为 r。

具体实现

  1. 排序：将城市和信号发射塔的位置分别排序。
  2. 二分查找：对于每个城市，使用二分查找在信号发射塔的位置中找到离它最近的信号发射塔。
  3. 计算距离：计算每个城市到最近信号发射塔的距离，并取最大值作为 r。

代码实现

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<int> a(n), b(m);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    for (int i = 0; i < m; ++i) {
        cin >> b[i];
    }

    // 排序
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

    int maxDist = 0;
    for (int i = 0; i < n; ++i) {
        // 使用二分查找找到离 a[i] 最近的信号发射塔
        auto it = lower_bound(b.begin(), b.end(), a[i]);
        int dist = INT_MAX;
        if (it != b.end()) {
            dist = abs(a[i] - *it);
        }
        if (it != b.begin()) {
            dist = min(dist, abs(a[i] - *(it - 1)));
        }
        maxDist = max(maxDist, dist);
    }

    cout << maxDist << "\n";

    return 0;
}

代码解释

  1. 输入处理：

    • 读取城市数量 n 和信号发射塔数量 m。
    • 读取城市位置 a 和信号发射塔位置 b。

  2. 排序：

    • 将城市位置 a 和信号发射塔位置 b 分别排序。

  3. 二分查找：

    • 对于每个城市 a[i]，使用 lower_bound 在 b 中找到离它最近的信号发射塔。
    • 计算该城市到最近信号发射塔的距离，并更新最大距离 maxDist。

  4. 输出结果：

    • 输出 maxDist，即最小的 r。

复杂度分析

  1. 时间复杂度：

    • 排序的时间复杂度为 O(n log n + m log m)。
    • 对于每个城市，使用二分查找的时间复杂度为 O(log m)。
    • 总时间复杂度为 O(n log n + m log m + n log m)。

  2. 空间复杂度：

    • 使用两个向量存储城市和信号发射塔的位置，空间复杂度为 O(n + m)。

总结

通过排序和二分查找，我们成功解决了这个问题。这道题目考察了二分查找的应用能力，同时也提醒我们在实际生活中要合理规划资源，最大化收益！希望这篇题解能帮助你更好地理解题目！