专栏文章

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

zzhouzihan20110620
B4242题解参与者 2已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@miptw630
此快照首次捕获于
2025/12/03 17:52
3 个月前
此快照最后确认于
2025/12/03 17:52
3 个月前
查看原文

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

题目解析

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

做法优化

考虑最朴素的做法：从小到大枚举 rr，判断每一个 aia_i 是否满足上述条件。这样的时间复杂度最坏可以达到 O(nm)O(nm)（系数常数为 2×1092 \times 10^9），显然不可行。
我们要考虑两层优化：
第一层即为对于 rr 的枚举，对于求 rr 的最小值，可以显然想到二分，这样就可以将 rr 的枚举量简化为 log⁡22×109\log_2 2\times 10^9，就没有那么大的常数了，然而到这里时间复杂度仍在 O(nm)O(nm)。
第二层优化是判断是否满足条件，可以不用遍历每一个 aia_i 和 bjb_j，同理我们可以二分找离 aia_i 最近的点 bjb_j，这样就能单次 log⁡2m\log_2 m 求距 aia_i 最近的 bib_i，因为显然对 aia_i 而言只有离其最近的 bib_i 点可能会对答案产生影响。
这两层优化考虑完成，就可以得到 O(nlog⁡m)O(n \log m) 的正确代码，但是当我们考虑完第二层优化后，能很自然的想到可不可以利用这种找最近 bib_i 点的方法来直接对答案产生贡献。具体的，我们考虑对于 aia_i，想要其满足条件，就要让 r≥∣bj−ai∣r \ge \lvert b_j-a_i\rvert，其中 bjb_j 是二分求得的离 aia_i 最近的点，那么就让 rr 不断对上述式子取最大值即可，时间复杂度为 O(nlog⁡m)O(n \log m)。
可以证明最优复杂度即为 O(nlog⁡m)O(n \log m)，此外还有同级复杂度的最优复杂度 O(nlog⁡n+mlog⁡m)O(n \log n + m \log m)，所以本质上应该没有线性做法，瓶颈在排序。

详细代码

CPP
//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;
}
CPP
//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;
}
CPP
//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;
}
CPP
//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;
}
CPP
//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。

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...