CF1479B1 Painting the Array II
题目描述
给定一个数组 \(a\), 你将将 \(a_i\) 染为 \(b_i\) 色, 其中 \(b\) 是由你指定的一个 01 数组。将 \(a\) 数组中被染成 0 色的数字取出来并依在 \(a\) 中出现的顺序排列, 组成数组 \(a^{(0)}\). 同理, 将 \(a\) 数组中被染成 1 色的数字取出来并依在 \(a\) 中出现的顺序排列, 组成数组 \(a^{(1)}\).
我们定义 \(seg(c)\) 是一个正整数, 其中 \(c\) 是一个数组, \(seg(c)\) 的值为在我们将 \(c\) 中相邻的所有相同元素合并后, \(c\) 数组的大小. 例如, \(seg([1, 1, 4, 5, 1, 4]) = |[1, 4, 5, 1, 4]|=5\).
最大化 \(seg(a^{(0)})+seg(a^{(1)})\).
题解
贪心。显然我们维护两个队列，每次去看末尾的数与 \(a_i\) 的关系，有以下四种：
- \(lst_1 = a_i, lst_2 \ne a_i\)，此时我们显然塞进队列 \(2\)。
- \(lst_2 = a_i, lst_1 \ne a_i\)，此时我们显然塞进队列 \(1\)。
- \(lst_1 = lst_2 = a_i\)，此时随便找一个塞进去不会影响答案。
- \(lst_1 \ne a_i,lst_2 \ne a_i\)，此时怎么办？此时不同的放置方式虽然对当前答案无影响，但可能会影响后续答案。
后续答案是怎么被影响的呢？如果某个队列，队尾元素的下一次出现位置更早，肯定把这个元素塞进去把两个相同的数隔开。至于下一次出现位置更远的，以后再说嘛。
所以只需要维护每一个数下一个相同元素的出现位置即可。
Code
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int M = 1e5 + 5;
int a[M], nxt[M], idx[M];
signed main(){int n, res = 0;cin >> n;for(int i = 1; i <= n; i++) cin >> a[i], idx[i] = n + 1;vector<pair<int, int>>vec1, vec2;for(int i = n; i >= 1; i--) {nxt[i] = idx[a[i]];idx[a[i]] = i;}vec1.push_back(make_pair(n + 1, 0));vec2.push_back(make_pair(n + 1, 0));for(int i = 1; i <= n; i++){int bk1 = vec1.back().second, bk2 = vec2.back().second;pair<int, int> ms = make_pair(nxt[i], a[i]);if(bk1 == a[i]){if(a[i] != bk2) res++;vec2.push_back(ms);}else if(bk2 == a[i]){if(a[i] != bk1) res++;vec1.push_back(ms);}else {res++;if(vec1.back().first < vec2.back().first) vec1.push_back(ms);else vec2.push_back(ms);}}cout << res;return 0;
}