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

如果你做过最小路径覆盖问题的话，应该可以看出来这题可以建模为二分图匹配。具体的，对于每个数，拆成左部点和右部点。我们定义

(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)

。

CPP

#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;
}

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

文章操作

相关推荐

评论

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