奶龙与贝利亚
题面
\(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;
}