专栏文章

题解：AT_abc215_f [ABC215F] Dist Max 2

lljk8886
AT_abc215_f题解参与者 2已保存评论 2

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@mimz0z2h
此快照首次捕获于
2025/12/01 17:53
3 个月前
此快照最后确认于
2025/12/01 17:53
3 个月前
查看原文
NOIP2025 加油！
题目传送门 AT

题目大意

有 nn 个点 (xi,yi)(x_i, y_i)，求所有不同的两个点的“距离”的最大值。
“距离”定义：对于两个点 i,ji, j，这两个点的距离为 min⁡(∣xi−xj∣,∣yi−yj∣)\min(|x_i - x_j|, |y_i - y_j|)。
n≤2×105n \le 2 \times 10^5 。

题目分析

看到最小值最大，先想二分答案。
考虑当前二分到 midmid，满足的要求为 min⁡(∣xi−xj∣,∣yi−yj∣)≥mid\min(|x_i - x_j|, |y_i - y_j|) \ge mid，即 ∣xi−xj∣≥mid|x_i - x_j| \ge mid 且 ∣yi−yj∣≥mid|y_i - y_j| \ge mid。
因为有两个东西需要处理，非常不好弄。那么我们就先定住一个。我们不妨把 xx 定住。
按 xx 从小到大排序，用双指针找出满足 xr−xl≥midx_r - x_l \ge mid，那么 ∣xi−xj∣≥mid|x_i - x_j| \ge mid 就满足了，其中 i≤l,r≤ji \le l, r \le j。
接下来处理 yy。我们求出 ll 前面和 rr 后面的最值，判断前缀最大值减去后缀最小值或者后缀最大值减去前缀最小值大于等于 midmid 即可。
时间复杂度 O(nlog⁡V)\mathcal{O}(n \log V)，其中 VV 为 x,yx, y 的值域。

code

CPP
#include <bits/stdc++.h>
#define ft first
#define sd second
#define endl '\n'
#define pb push_back
#define md make_pair
#define gc() getchar()
#define pc(ch) putchar(ch)
#define umap unordered_map
#define pque priority_queue
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 bint;
typedef pair<int, int> pii;
typedef pair<pii, int> pi1;
typedef pair<pii, pii> pi2;
const ll INF = 0x3f3f3f3f;
const db Pi = acos(-1.0);
inline ll read()
{
	ll res = 0, f = 1; char ch = gc();
	while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : f), ch = gc();
	while (ch >= '0' && ch <= '9') res = (res << 1) + (res << 3) + (ch ^ 48), ch = gc();
	return res * f;
}
inline void write(ll x)
{
	if (x < 0) x = -x, pc('-');
	if (x > 9) write(x / 10);
	pc(x % 10 + '0');
}
inline void writech(ll x, char ch) { write(x), pc(ch); }
const int N = 2e5 + 5;
int lmin[N], lmax[N], rmin[N], rmax[N]; // 前缀 / 后缀 最小值 / 最大值
struct node {
	int x, y;
} a[N];
bool cmp(node x, node y) { return x.x < y.x; }
int n;
bool check(int mid)
{
	for (int i = 1, j = 1; i <= n; i++)
	{
		while (j < n && a[j].x - a[i].x < mid) j++;
		// 满足 |x_i - x_j| >= mid
		if (a[j].x - a[i].x < mid) break;
		if (lmax[i] - rmin[j] >= mid || rmax[j] - lmin[i] >= mid) return true; 
	}
	return false;
}
int main()
{
	n = read();
	for (int i = 1; i <= n; i++) a[i].x = read(), a[i].y = read();
	sort(a + 1, a + n + 1, cmp);
	lmin[0] = INF;
	for (int i = 1; i <= n; i++) lmin[i] = min(lmin[i - 1], a[i].y), lmax[i] = max(lmax[i - 1], a[i].y);
	rmin[n + 1] = INF;
	for (int i = n; i >= 1; i--) rmin[i] = min(rmin[i + 1], a[i].y), rmax[i] = max(rmax[i + 1], a[i].y);
	int l = 0, r = 1e9, ans = 0;
	while (l <= r)
	{
		int mid = (l + r) >> 1;
		if (check(mid)) l = mid + 1, ans = mid;
		else r = mid - 1;
	}
	write(ans);
	return 0;
}

// NOIP2025 rp++

评论

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

正在加载评论...