AT_joisc2021_e 题解

· · 题解

好题！坑题！

前置知识：曼哈顿转切比雪夫。很好理解，不再赘述。

转化完之后，考虑使用二分法求出第 k 小的距离 ans。操作步骤如下（假设当前二分的值是 mid）：

注意到切比雪夫距离 \max(|x_1-x_2|,|y_1-y_2|)\le mid 的充要条件是 |x_1-x_2|\le mid 且 |y_1-y_2|\le mid，接下来想办法把两条限制消除一个。

那么可以首先把所有点按照横坐标排序，保证单调不降。接下来扫一遍所有的点，对于当前点 i，把它前面的满足条件 |x_i-x_j|\le mid 的点 j 加入一个 set 里面，这是横坐标满足条件的。接下来在这个范围内找到纵坐标满足条件的，这个条件等价于 y_i-mid\le y_j\le y_i+mid，利用 set 的有序性可以很方便的查找。

为什么只算前面的啊？因为这样可以保证一个点对的答案会且仅会被靠后的点计算到，不重不漏。

这样找到了所有距离小于等于 mid 的点对了，把他们统一存进一个数组里面，如果个数大于等于 k，那么合法，将距离向小计算；否则向大。

接下来是踩坑时间。首先放上代码：

#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 ; 的剪枝过程，这就导致你在搜索 res 的时候可能确实搜出来了 k 个距离小于它的点对，但是不是最小的，后面有的更小的没有放进去就直接返回了。

check (res - 1) 的正确性？

注意到因为 check (res - 1) < k，所以此时一定把所有的答案全部搜出来了，且他们是最小的。又因为 check (res) >= k，所以一定可以用 res 这个值把剩下的补完。