题解：AT_abc457_g [ABC457G] Catch All Apples

Shellchen · 2026-05-10 19:44:15 · 题解

注意到，一个机器人可以从苹果 i 移动到苹果 j 的条件是：|X_i-X_j|\le T_j-T_i。拆开绝对值就有 T_i-T_j \le X_i-X_j \le T_j-T_i，即 X_i-T_i\ge X_j-T_j 且 X_i+T_i \le X_j+T_j。

令 L_i=X_i-T_i,R_i=X_i+T_i。那么 i 能走到 j 的条件就是 L_i \ge L_j 且 R_i \le R_j。那么根据 Dilworth 定理，答案就是按 R_i<R_j 第一关键字，L_i>L_j 第二关键字排序苹果序列后，L 的最长上升子序列。

LIS 可以使用贪心 + 二分求，复杂度 O(n \log n)。 :::success[code]

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define lowbit(x) ((x)&(-(x)))
const int N=3e5+10,mod=998244353;
pair<int,int>a[N]; 
bool cmp(pair<int,int>x,pair<int,int>y)
{
    if(x.fi!=y.fi) return x.fi<y.fi;
    return x.se>y.se;
}
int cur,b[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int t,x;
        cin>>t>>x;
        a[i]={x-t,x+t};
    }
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        int p=lower_bound(b+1,b+cur+1,a[i].se)-b;
        if(p==cur+1) b[++cur]=a[i].se;
        else b[p]=a[i].se;
    }
    cout<<cur;
    return 0; 
}

:::