0%

[CF1479B] Painting the Array

题目

题目链接

题目链接

题目大意: 给定序列 $\{a_n\}$, 对这个序列的每个元素都将其按相对顺序添加到 $a^0$ 或 $a^1$ 数组中. 求出两个新数组在合并连续相同的数后长度和的最大值和最小值. $1 \le n \le 10^5$.

思路

先思考怎么求出最大值.

考虑贪心. 设 $n_0$ 为当前 $a^0$ 长度, $n_1$ 为当前 $a^1$ 长度.

如果 $a_i = a^0_{n_0} \neq a^1_{n_1}$, 显然将 $a_i$ 加入 $a^0$.

反之则加入 $a^1$.

若 $a_i \neq a^0_{n_0}$ 且 $a_i \neq a^1_{n_1}$, 放到哪边都没关系.

若 $a_i = a^0_{n_0} = a^1_{n_1}$, 这时我们需要考虑将 $a_i$ 添加到哪里. 此时我们引进一个东西 $nxt(i)$, 表示 $a_i$ 下一次出现的位置. 显然, 我们要将 $a_i$ 加入 $nxt$ 较小的那一方, 不然就有可能在下一步得不到最优解.

求最小值的方法只需要跟上面的方法反着来即可.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

template <class T>
inline void read(T &x) {
x = 0;
int f = 0;
char ch = getchar();
while (!isdigit(ch)) { f |= ch == '-'; ch = getchar(); }
while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
x = f ? -x : x;
return ;
}

typedef unsigned long long uLL;
typedef long long LL;

int a[100010], nxt[100010], pos[100010], a1[100010], a2[100010];
int n, n1, n2, ans;

int main() {
read(n);
for (int i = 1; i <= n; ++i) read(a[i]);
for (int i = n; i >= 1; --i) {
nxt[i] = pos[a[i]] ? pos[a[i]] : 114514;
pos[a[i]] = i;
}
nxt[0] = 114514;
for (int i = 1; i <= n; ++i) {
if (a[a1[n1]] != a[i] && a[a2[n2]] != a[i]) {
if (nxt[a1[n1]] < nxt[a2[n2]]) {
a1[++n1] = i;
} else {
a2[++n2] = i;
}
++ans;
} else if (a[a1[n1]] != a[i]) {
a1[++n1] = i;
++ans;
} else if (a[a2[n2]] != a[i]) {
a2[++n2] = i;
++ans;
} else {
a1[++n1] = i;
}
}
printf("%d\n", ans);
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

template <class T>
inline void read(T &x) {
x = 0;
int f = 0;
char ch = getchar();
while (!isdigit(ch)) { f |= ch == '-'; ch = getchar(); }
while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
x = f ? -x : x;
return ;
}

typedef unsigned long long uLL;
typedef long long LL;

int a[100010], nxt[100010], pos[100010], a1[100010], a2[100010];
int n, n1, n2, ans;

int main() {
read(n);
for (int i = 1; i <= n; ++i) read(a[i]);
for (int i = n; i >= 1; --i) {
nxt[i] = pos[a[i]] ? pos[a[i]] : 114514;
pos[a[i]] = i;
}
nxt[0] = 114514;
for (int i = 1; i <= n; ++i) {
if (a[a1[n1]] != a[i] && a[a2[n2]] != a[i]) {
if (nxt[a1[n1]] > nxt[a2[n2]]) {
a1[++n1] = i;
} else {
a2[++n2] = i;
}
++ans;
} else if (a[a1[n1]] == a[i]) {
a1[++n1] = i;
} else if (a[a2[n2]] == a[i]) {
a2[++n2] = i;
} else {
a1[++n1] = i;
++ans;
}
}
printf("%d\n", ans);
return 0;
}