专栏文章

AT_joisc2021_e 题解

MMelo_qwq怦然心动
AT_joisc2021_e题解参与者 3已保存评论 2

文章操作

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

当前评论
2 条
当前快照
1 份
快照标识符
@miqrsz68
此快照首次捕获于
2025/12/04 09:41
3 个月前
此快照最后确认于
2025/12/04 09:41
3 个月前
查看原文
好题！坑题！
前置知识：曼哈顿转切比雪夫。很好理解，不再赘述。
转化完之后，考虑使用二分法求出第 kk 小的距离 ansans。操作步骤如下（假设当前二分的值是 midmid）：
注意到切比雪夫距离 max⁡(∣x1−x2∣,∣y1−y2∣)≤mid\max(|x_1-x_2|,|y_1-y_2|)\le mid 的充要条件是 ∣x1−x2∣≤mid|x_1-x_2|\le mid 且 ∣y1−y2∣≤mid|y_1-y_2|\le mid，接下来想办法把两条限制消除一个。
那么可以首先把所有点按照横坐标排序，保证单调不降。接下来扫一遍所有的点，对于当前点 ii，把它前面的满足条件 ∣xi−xj∣≤mid|x_i-x_j|\le mid 的点 jj 加入一个 set 里面，这是横坐标满足条件的。接下来在这个范围内找到纵坐标满足条件的，这个条件等价于 yi−mid≤yj≤yi+midy_i-mid\le y_j\le y_i+mid，利用 set 的有序性可以很方便的查找。
为什么只算前面的啊？因为这样可以保证一个点对的答案会且仅会被靠后的点计算到，不重不漏。
这样找到了所有距离小于等于 midmid 的点对了，把他们统一存进一个数组里面，如果个数大于等于 kk，那么合法，将距离向小计算；否则向大。
接下来是踩坑时间。首先放上代码：
CPP
#include <bits/stdc++.h>
#define f(i ,m ,n ,x) for (int i = (m) ; i <= (n) ; i += (x))
using cint = const int ; using ll = long long ;

template < typename T > inline void read ( T &x ) {
	x = 0 ;
	bool flag (0) ; char ch = getchar () ;
	while (! isdigit (ch))
	{ flag = ch == '-' ; ch = getchar () ;}
	while (isdigit (ch))
	{ x = (x << 1) + (x << 3) + (ch ^ 48) ; ch = getchar () ;}
	flag ? x = - x : 0 ;
} template < typename T ,typename ...Args > 
inline void read ( T &x ,Args &...tmp ) { read (x) ,read (tmp...) ;}

cint N = 3e5 + 7 ; const ll inf = -8000000007ll ;
int n ,k ,tot ; ll ans[N] ;
struct point {
	ll x ,y ;
	bool operator < (const point &cmp) 
	const { return y < cmp.y ;}
} p[N] ;
using iter = std :: multiset < point > :: iterator ;
inline bool cmp (const point & ,const point &) ;

inline bool check (const ll) ;

int main () {
	read (n ,k) ;
	f (i ,1 ,n ,1) {
		ll x ,y ; read (x ,y) ;
		p[i] = (point) {x - y ,x + y} ; // 转切比雪夫
	} std :: sort (p + 1 ,p + n + 1 ,cmp) ;
	
	ll l = 0ll ,r = - inf ,mid ,res ;
	while (l <= r) {
		mid = l + r >> 1 ;
		if (check (mid)) r = mid - 1 ,res = mid ;
		else l = mid + 1 ;
	} check (res - 1) ;
	std :: sort (ans + 1 ,ans + tot + 1) ;
	int i ;
	for (i = 1 ; i <= tot ; i ++) 
		std :: cout << ans[i] << '\n' ;
	for(; i <= k ; i ++) std :: cout << res << '\n' ;
	return 0 ;
}

inline bool cmp (const point &x ,const point &y) 
{ return x.x < y.x ;}

inline bool check (const ll mid) {
	tot = 0 ;
	static std :: queue < int > q ;
	static std :: multiset < point > se ;
	while (! q.empty ()) q.pop () ; se.clear () ;
	f (i ,1 ,n ,1) {
		while (! q.empty () && p[i].x - p[q.front ()].x > mid) {
			iter it = se.find (p[q.front ()]) ; se.erase (it) ;
			q.pop () ; // 用队列维护有多少的点在集合里面
		} iter it ; 
		if (se.empty ()) goto her ; 
		it = se.lower_bound ((point) {inf ,p[i].y - mid}) ;
		for ( ; it != se.end () && it -> y <= p[i].y + mid ; it ++) {
			ans[++ tot] = std :: max 
			(std :: abs (p[i].x - it -> x) ,std :: abs (p[i].y - it -> y)) ;
			if (tot >= k) return true ;
		} her : ;
		se.insert (p[i]) ;
		q.push (i) ;
	} return false ;
}
然后你发现我的二分写的非常繁琐啊，我也这么觉得。然后你可能直接把 check (res - 1) 和后面的那一坨东西改成 check (res) 然后直接把 ans 数组输出了。
然后你错了一些点。
这不显然是不行的，因为我们有 if (tot >= k) return true ; 的剪枝过程，这就导致你在搜索 resres 的时候可能确实搜出来了 kk 个距离小于它的点对，但是不是最小的，后面有的更小的没有放进去就直接返回了。
check (res - 1) 的正确性？
注意到因为 check (res - 1) < k，所以此时一定把所有的答案全部搜出来了，且他们是最小的。又因为 check (res) >= k，所以一定可以用 resres 这个值把剩下的补完。

评论

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

正在加载评论...