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

· · 题解

题目解析+做法优化+详细代码

题目解析

题目描述很清晰，就是要找最小的 r 使得对于任意的 a_i(1 \le i \le n)，满足 \exists \lvert b_j-a_i \rvert \le r(1 \le j \le m)。

做法优化

考虑最朴素的做法：从小到大枚举 r，判断每一个 a_i 是否满足上述条件。这样的时间复杂度最坏可以达到 O(nm)（系数常数为 2 \times 10^9），显然不可行。

我们要考虑两层优化：

第一层即为对于 r 的枚举，对于求 r 的最小值，可以显然想到二分，这样就可以将 r 的枚举量简化为 \log_2 2\times 10^9，就没有那么大的常数了，然而到这里时间复杂度仍在 O(nm)。

第二层优化是判断是否满足条件，可以不用遍历每一个 a_i 和 b_j，同理我们可以二分找离 a_i 最近的点 b_j，这样就能单次 \log_2 m 求距 a_i 最近的 b_i，因为显然对 a_i 而言只有离其最近的 b_i 点可能会对答案产生影响。

这两层优化考虑完成，就可以得到 O(n \log m) 的正确代码，但是当我们考虑完第二层优化后，能很自然的想到可不可以利用这种找最近 b_i 点的方法来直接对答案产生贡献。具体的，我们考虑对于 a_i，想要其满足条件，就要让 r \ge \lvert b_j-a_i\rvert，其中 b_j 是二分求得的离 a_i 最近的点，那么就让 r 不断对上述式子取最大值即可，时间复杂度为 O(n \log m)。

可以证明最优复杂度即为 O(n \log m)，此外还有同级复杂度的最优复杂度 O(n \log n + m \log m)，所以本质上应该没有线性做法，瓶颈在排序。

详细代码

//O(2*10^9nm)30pts
#include <iostream>
#include <algorithm>
using namespace std;
long long n, m, a[100005], b[100005], r;
int main()
{
    cin >> n >> m;
    for (int i = 1;i <= n;i++)
    {
        cin >> a[i];
    }
    for (int i = 1;i <= m;i++)
    {
        cin >> b[i];
    }
    while (1)
    {
        bool flag = 1;
        for (int i = 1;i <= n;i++)
        {
            bool nflag = 0;
            for (int j = 1;j <= m;j++)
            {
                if (abs(b[j] - a[i]) <= r)
                {
                    nflag = 1;
                    break;
                }
            }
            if (!nflag)
            {
                flag = 0;
                break;
            }
        }
        if (flag)
        {
            break;
        }
        r++;
    }
    cout << r;
    return 0;
}
//O(30nm)70pts
#include <iostream>
#include <algorithm>
using namespace std;
long long n, m, a[100005], b[100005], l, r, mid, ans;
bool check(long long x)
{
    bool flag = 1;
    for (int i = 1;i <= n;i++)
    {
        bool nflag = 0;
        for (int j = 1;j <= m;j++)
        {
            if (abs(b[j] - a[i]) <= x)
            {
                nflag = 1;
                break;
            }
        }
        if (!nflag)
        {
            flag = 0;
            break;
        }
    }
    return flag; 
}
int main()
{
    cin >> n >> m;
    for (int i = 1;i <= n;i++)
    {
        cin >> a[i];
    }
    for (int i = 1;i <= m;i++)
    {
        cin >> b[i];
    }
    l = 0;
    r = 2e9 + 1;
    while (l <= r)
    {
        mid = (l + r) >> 1;
        if (check(mid))
        {
            ans = mid;
            r = mid - 1;
        }
        else
        {
            l = mid + 1;
        }
    }
    cout << ans;
    return 0;
}
//O(30nlogm)100pts
#include <iostream>
#include <algorithm>
using namespace std;
long long n, m, a[100005], b[100005], l, r, mid, ans;
bool check(long long x)
{
    bool flag = 1;
    for (int i = 1;i <= n;i++)
    {
        long long p = lower_bound(b + 1, b + m + 1, a[i]) - b;
        if (a[i] - b[p - 1] > x && b[p] - a[i] > x)
        {
            flag = 0;
            break;
        }
    }
    return flag; 
}
int main()
{
    cin >> n >> m;
    for (int i = 1;i <= n;i++)
    {
        cin >> a[i];
    }
    b[0] = -9e18;
    for (int i = 1;i <= m;i++)
    {
        cin >> b[i];
    }
    sort(b + 1, b + m + 1);
    b[m + 1] = 9e18;
    l = 0;
    r = 2e9 + 1;
    while (l <= r)
    {
        mid = (l + r) >> 1;
        if (check(mid))
        {
            ans = mid;
            r = mid - 1;
        }
        else
        {
            l = mid + 1;
        }
    }
    cout << ans;
    return 0;
}
//O(nlogm)100pts
#include <iostream>
#include <algorithm>
using namespace std;
long long n, m, a[100005], b[100005], ans;
int main()
{
    cin >> n >> m;
    for (int i = 1;i <= n;i++)
    {
        cin >> a[i];
    }
    sort(a + 1, a + n + 1);
    b[0] = -9e18;
    for (int i = 1;i <= m;i++)
    {
        cin >> b[i];
    }
    sort(b + 1, b + m + 1);
    b[m + 1] = 9e18;
    for (int i = 1;i <= n;i++)
    {
        long long p = lower_bound(b + 1, b + m + 1, a[i]) - b;
        ans = max(ans, min(a[i] - b[p - 1], b[p] - a[i]));
    }
    cout << ans;
    return 0;
}
//O(nlogn+mlogm+n+m)100pts
#include <iostream>
#include <algorithm>
using namespace std;
long long n, m, a[100005], b[100005], nowi, ans;
int main()
{
    cin >> n >> m;
    for (int i = 1;i <= n;i++)
    {
        cin >> a[i];
    }
    sort(a + 1, a + n + 1);
    b[0] = -9e18;
    for (int i = 1;i <= m;i++)
    {
        cin >> b[i];
    }
    sort(b + 1, b + m + 1);
    b[m + 1] = 9e18;
    for (int i = 1;i <= n;i++)
    {
        while (b[nowi] < a[i])
        {
            nowi++;
        }
        ans = max(ans, min(a[i] - b[nowi - 1], b[nowi] - a[i]));
    }
    cout << ans;
    return 0;
}

至此，本题讲解完毕。

蒟蒻的第一篇题解，求过QAQ。