题解：CF2161D Locked Out

Double_Air · 2026-07-21 16:44:36 · 题解

题解：CF2161D Locked Out

题目简述：一个好数组，其中的值相差为 1 的元素不能同时存在。再让你删除几个数，使得这个数组成为一个好数组。

思路还是比较好想的，把数组中的每个数都看成一个点，如果某两个位置上的数相差为 1，就在它们之间连一条边。

那么题目就变成：选最少的点（也就是删除最少的数），让所有的边都消失。

看到这，题目就成了一个最小点覆盖问题。

由于一条边永远连接的是一个奇数和一个偶数。它绝对不会连接两个奇数，也不会连接两个偶数。

因此满足二分图的定义。从而根据柯尼希定理，二分图的最小点覆盖大小等于最大匹配大小。所以，我们只要算出这个图的最大匹配数，就是答案了。

把问题转化为求最大匹配后，一般的做法是用匈牙利算法，但会超时。这道题的图有特殊的“分层”结构，使得我们可以用贪心来求最大匹配：

• 所有值为 1 的点都在第 1 层，值为 2 的点都在第 2 层，依此类推。并且，第 i 层的点只会向第 i+1 层中，位置更大的点连边。
• 所以，我们可以从第 i 层开始，从大到小（也就是从后往前）尝试将每个点与下一层中位置最大的那个点进行匹配。这样贪心能保证匹配数最大。

代码如下（时间复杂度 O(n)）：

#include<bits/stdc++.h>
#define rep(z,x,y) for(int z=x;z<=y;z++)
#define drep(z,x,y) for(int z=x;z>=y;z--)
#define endl '\n'
using namespace std;
const int MAXN=3e5+5;
int n,a[MAXN];
vector<int> ed[MAXN];
void solve(){
    cin>>n;
    rep(i,1,n){
        cin>>a[i];
        ed[i].clear();
    }
    rep(i,1,n) ed[a[i]].push_back(i);
    int ans=0;
    rep(i,1,n-1){
        int j=(int)ed[i].size()-1;
        while(j>=0&&!ed[i+1].empty()){
            if(ed[i][j]<ed[i+1].back()){
                ed[i+1].pop_back();
                ans++;
            }
            j--;
        }
    }
    cout<<ans<<'\n';
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}