这年头怎么二分图最大匹配都能用贪心求了啊！

· · 题解

如果你做过最小路径覆盖问题的话，应该可以看出来这题可以建模为二分图匹配。具体的，对于每个数，拆成左部点和右部点。我们定义 (i,j) 匹配，当且仅当 i < j，且 \left| a_i - a_j \right| = 1。对于每一组匹配的 (i,j)，让 i 的左部点向 j 的右部点连一条边，表示合并了一条路径。这样，整个二分图的最大匹配数就是最多能合并的路径数。用 n 减去这个匹配数即可。

显然直接跑二分图最大匹配是不行的，就算你使用一些技巧成功把边数压到了 O(n) 范围，一个用网络流跑的二分图最大匹配的复杂度怎么也不会低于 O(n \sqrt{n}) 的。于是 TLE 了。

这启示我们，应该考虑这张图的特殊性质。

我们注意到，1 只能和 2 匹配，而对于 3 而言，它不仅能和 2 匹配，还能和 4 匹配。于是，我们大胆猜测，一定优先让 1 匹配上。同时我们考虑让前面的 1 把更靠前的 2 匹配掉。以上是对于左部点匹配的情况。对于右部点，我们反过来，让每个 1 最右侧的 2。

为什么这样一定不劣呢？假定原先有一个位置在 A 的 1 和一个位置在 A' 的数匹配上了，另外一个位置 B 的 2 和一个位置 B' 的数匹配了。其中，A 和 B' 是左部点，A' 和 B 是右部点，且四个点互不相同。现在我们尝试让 A 与 B 匹配。显然，A' 位置上的数也是 2，而根据前提条件，B 是离自己最近的 1，而既然 B' 能与 B 匹配，则它一定在 B 前，自然也就在 A' 前，所以 A' 和 B 总是可以匹配，匹配数没有减少。对于右部点的情况是同理的。

当我们把所有的 1 处理完之后，剩余的最小的数变为 2，情况和上面是类似的。进行相同的处理即可。

实现时考虑维护每个数出现的位置和其是否作为左部点（以及右部点）被匹配。每个上述序列至多被遍历两遍，且所有序列中元素数量的总和为 n，故时间复杂度 O(n)。

#include<bits/stdc++.h>
using namespace std;
const int Maxn=1000000;
int T;
int n,ans;
int nums[Maxn+10];
vector<vector<pair<int,bool> > > p1,p2;
void merge(int x,int y)
{
    int ptr1=0,ptr2=0;
    while(true)
    {
        while(ptr1<p1[x].size()&&!p1[x][ptr1].second) ptr1++;
        if(ptr1==p1[x].size()) return;
        while(ptr2<p2[y].size()&&(!p2[y][ptr2].second||p2[y][ptr2].first<p1[x][ptr1].first)) ptr2++;
        if(ptr2==p2[y].size()) return;
        ans--;
        p1[x][ptr1].second=false;
        p2[y][ptr2].second=false;
    }
    return;
}
void merge2(int x,int y)
{
    int ptr1=0,ptr2=0;
    stack<int> stk;
    while(true)
    {
        while(ptr2<p2[x].size()&&!p2[x][ptr2].second) ptr2++;
        if(ptr2==p2[x].size()) return;
        while(ptr1<p1[y].size()&&p1[y][ptr1].first<p2[x][ptr2].first)
        {
            if(p1[y][ptr1].second) stk.push(ptr1);
            ptr1++;
        }
        if(!stk.empty())
        {
            ans--;
            int res=stk.top();
            stk.pop();
            p2[x][ptr2].second=false;
            p1[y][res].second=false;
        }
        ptr2++;
    }
    return;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>T;
    while(T--)
    {
        cin>>n;
        p1.clear(),p2.clear();
        p1.resize(2*n+5),p2.resize(2*n+5);
        for(int i=1;i<=n;i++)
        {
            cin>>nums[i];
            p1[nums[i]].push_back({i,true});
            p2[nums[i]].push_back({i,true});
        }
        ans=n;
        for(int i=1;i<2*n;i++)
        {
            merge(i,i+1);
            merge2(i,i+1);
        }
        cout<<ans<<"\n";
    }
    return 0;
}