题解：CF2161D Locked Out

简单（迫真）做法

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

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

接下来观察图的形态，把值相同的分一层，第

i

层里的点都有

a_u=i

。

第

i

层的点

u

会向

i+1

层里所有

v>u

的点

v

连边。

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

时间复杂度

O(n)

。

CPP

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

题解：CF2161D Locked Out

文章操作

相关推荐

评论

题解：CF2161D Locked Out