奶龙与贝利亚
题面
\(n\) 个生物排成一排,每个生物是奶龙或者贝利亚。
给定数组 \(a_1,a_2, \cdots, a_n\),有约束:
- 若第 \(i\) 个位置是奶龙,那么前面恰好有 \(a_i\) 个奶龙。
- 若第 \(i\) 个位置是贝利亚,那么前面至多有 \(a_i\) 个奶龙。
\(1 \le n \le 2 \times 10^5 , 0 \le a_i \le n\)
题解
这唐题在考场上给我暴击了。
对于放奶龙的这个约束,其实是挺强的,我们也不难发现,把放奶龙的 \(a_i\) 拎出来,会形成一个 \(0,1,\cdots\) 的序列。
如果只是这样的话,那就是最长上升子序列,但是这道题还有贝利亚的约束。
手模一下样例:0 1 2 0 1
发现最多只能在最后两个位置放两只奶龙,对于 \(a_i\) 相同的位置,我们只能选最后的一个放奶龙,否则后面就放不了贝利亚了。
那么思路就很简单了,对于每个 \(a_i\) 我们记录它最后出现的位置。
然后从小到大枚举 \(a_i\) ,记录上一个奶龙的位置,如果当前 \(pos > last\) 那就放,否则就再也放不了了。
时间复杂度 \(O(n)\)
code
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
#include <set>using namespace std;namespace michaele {const int N = 2e5 + 10;int n;int pos[N];void solve () {cin >> n;for (int i = 1; i <= n; i ++) {int x;cin >> x;pos[x] = i;}int la = 0;for (int i = 0; i < n; i ++) {if (pos[i] > la) {ans ++;la = pos[i];} else {break;}}cout << ans << endl;}
}int main () {michaele :: solve ();return 0;
}