题解：CF2161D Locked Out

· · 题解

简单（迫真）做法

把不符合要求的两个位置连一条边，原题变为最小点覆盖。

发现图是二分图，转最大匹配（资料）。

接下来观察图的形态，把值相同的分一层，第 i 层里的点都有 a_u=i。

第 i 层的点 u 会向 i+1 层里所有 v>u 的点 v 连边。

这启发我们贪心，层数从小到大，每层从大到小，贪心匹配下一层最大的。

时间复杂度 O(n)。

const int N = 3e5 + 5;
int n, a[N];
vector<int> e[N];
void solve() {
    read(n);
    FOR(i, 1, n) read(a[i]);
    FOR(i, 1, n) e[i].clear();
    FOR(i, 1, n) e[a[i]].pb(i);
    int ans = 0;
    FOR(i, 1, n - 1) {
        ROF(j, SZ(e[i]) - 1, 0) {
            if(e[i + 1].empty()) break;
            if(e[i][j] < e[i + 1].back()) {
                e[i + 1].pop_back();
                ans ++;
            }
        }
    }
    print(ans);
}