P11335题解

allenchoi · 2025-03-07 09:28:04 · 题解

科技：

set

思路：

考虑可以用一只手，先按按钮 i 再按按钮 j 的条件：

发现二式成立时一式显然成立。将绝对值拆开，得：

那么原问题等价于将原序列拆成尽量少的子序列，使得每个子序列中的元素都二位偏序地上升。
设 x_i=A_i+T_i,y_i=T_i-A_i，然后把所有元素按 x 排序，从小到大枚举，并维护所有的子序列。
当我们枚举到 i 时，如果此时所有子序列末尾一项的 y_j 都大于 y_i，那么我们必须新开一个子序列；
否则，找到所有满足 y_j\le y_i 的子序列中 y_j 最大的一个，然后将 i 加入该子序列中。
考虑正确性：不难发现我们只关心子序列个数以及它们末尾项的 y_j（越小越好）。无论我们选择哪个 j 进行操作，最终都会变成 y_i，而其余的 y_j 不变。而由于我们选择了 y_j 最大的一个进行操作，所以剩下的 y_j 肯定是更小的，因此这样操作一定是最优的。
于是我们可以用一个 set 维护所有子序列的末尾项，以便插入、删除、查前驱这些操作，时间复杂度单 \log。

代码：

#include <bits/stdc++.h>
#define pii pair <int,int>
#define fi first
#define se second
#define mkp make_pair
using namespace std;
const int N = 5e5 + 5;
int n,m,a[N],t[N];
pii p[N];
set <int> s;
set <int> :: iterator it;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= m;i++) scanf("%d",&t[i]);
    for(int i = 1;i <= m;i++) scanf("%d",&a[i]);
    for(int i = 1;i <= m;i++) p[i] = mkp(a[i] + t[i],t[i] - a[i]);
    sort(p + 1,p + m + 1);
    for(int i = 1;i <= m;i++)
    {
        if(!s.empty() && (*s.begin()) <= p[i].se)
        {
            it = s.upper_bound(p[i].se),it--;
            s.erase(it);
        }
        s.insert(p[i].se);
    }
    printf("%d\n",(int)s.size());
    return 0;
}