题解：AT_abc457_g [ABC457G] Catch All Apples

· · 题解

传送门

题解

对于两个苹果 (T_1,X_1) 和 (T_2,X_2) 来说，

一个机器人能同时接到它们当且仅当存在一条速度小于等于 1 的路径经过这两点。

故有

\left\vert X_2-X_1\right\vert\le\left\vert T_2-T_1\right\vert

这个式子。

令

u=T+X,v=T-X

变为切比雪夫距离。

变为

\max(\left\vert u_2-u_1\right\vert,\left\vert v_2-v_1\right\vert)\ge T_2-T_1

这个式子。

假设有 T_2\ge T_1 关系，则有 u_2\ge u_1,v_2\ge u_1 关系。

也就是说：同一个机器人能回收的苹果，在 (u,v) 平面上必须同时满足 u 和 v 不下降。

根据 Dilworth 定理：最小链覆盖等于最大反链的大小等于最长严格下降子序列的长度。

AC code:

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=3e5+5;
int n;
struct Node{
    int x,y;
    bool operator<(const Node &nd)const{
        return x==nd.x?y<nd.y:x>nd.x;
    }
};
Node a[N];
signed main(){
    //HAPPY!
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        int x,y;
        cin>>x>>y;
        a[i]={y-x,y+x};
    }
    sort(a+1,a+n+1);
    vector<int> res;
    for(int i=1;i<=n;i++){
        int val=-a[i].y;
        auto it=lower_bound(res.begin(),res.end(),val);
        if(it==res.end()){
            res.push_back(val);
        }
        else{
            *it=val;
        }
    }
    cout<<res.size()<<"\n";
    return 0;
}