Codeforces Round #700 (Div. 2) D2 Painting the Array II（最通俗易懂的贪心策略讲解）看不懂来打我 ~_b2. painting the array ii

整理的算法模板合集： ACM模板

点我看算法全家桶系列！！！

实际上是一个全新的精炼模板整合计划

---

整场比赛的A ~ E 6题全，全部题目超高质量题解链接：

Codeforces Round #700 (Div. 2) A ~ E ，6题全，超高质量良心题解【每日亿题】2021/2/8：

https://fanfansann.blog.csdn.net/article/details/113750433

最通俗易懂的贪心策略讲解，保证听懂！看不懂你来打我 ~

Codeforces Round #700 (Div. 2) D2 Painting the Array II

Problem 1479B2 - Painting the Array II

给你一个序列 $a$，请你将这个序列撕开分成两个序列 $a^{(0)}$ 和 $a^{(1)}$，使得将 $a^{(0)}$ 和 $a^{(1)}$ 合并所有相邻且相同的元素之后，两个序列剩余的元素个数和最小。

Solution

我们先按照上面 D1 的贪心策略分析。

我们首先设 $a^{(0)}$ 序列的最后一个元素为 $x$ ，$a^{(1)}$ 的最后一个元素为 $y$ 。

分类讨论，我们分别考虑什么情况的时候，把当前元素分配给哪一个序列会更优，使得序列最短。

对于当前准备去分配的元素 $z1$，以及 $z1$ 后面一位元素 $z2$。

(1) 首先考虑对前面的贡献

1. 当 x == y 时，上下两个序列给谁都无所谓
2. 当 x == z1 && y != z1 时，很明显分配给 $x$ 会更优。
3. 当 y == z1 && x != z1 时，很明显分配给 $y$ 会更优。

(2) 若上述条件均为达到就考虑对后面的贡献

1. 当 x == z2 && y != z2 时，很明显分配给 $y$ 会更优
2. 当 y == z2 && x != z2 时，同理很明显分配给 $x$ 会更优

最后一种情况：若x != z2 && y != z2，以及其他的所有剩余情况，这时候就有讲究了。

看上去放到哪里都区别不大，但是我们想要最终的答案尽可能地小，也就是让元素尽可能合并，也就是：

$a[i]$ 以后和 $x$ 相同的元素（假设是 $xx$）尽量能和 $x$ 合并，也就是以后 $x$ 后面都不添加数。

$a[i]$ 以后和 $y$ 相同的元素（假设是 $yy$）尽量能和 $y$ 合并， 也就是以后 $y$ 后面都不添加数。

但是我们总归是要在 $x$ 或者 $y$ 后面选择一个数放进去，假设我们放到了 $x$ 后面，这样也就断绝了后面的那个与 $x$ 相同的元素 $xx$ 与 $x$ 合并的可能性。

所以我们应该取两个队列末尾元素：$x$ 和 $y$ 中 与它们相同的数 $xx$ 或者 $yy$ 的距离更近的那个队列。

我们假设是 $y$ ，这样与 $y$ 相同的数 $yy$ 比与 $x$ 相同的数 $xx$ 距离更近，也就是一个一个来放的话，更先到达两个队列面前，是距离更短的那个数，也就意味着最终可以和 $y$ 合并的可能性就更大，因此我们就把 $a[i]$ 放到 $x$ 的后面，让 $y$ 去追逐合并的梦想 ~

应该很好理解，非常形象。

我们预处理一下下标 $i$ 的最近的下一个相同元素的下标 $\mathtt{n}\mathtt{e}\mathtt{x}[\mathtt{i}]$ 就行了，如何实现具体看代码，很好理解。

总结一下就是：

若x != z2 && y != z2，以及其他的所有剩余情况时：若nex[x] < nex[y] ，我们分配给 $y$ 更优

若x != z2 && y != z2，以及其他的所有剩余情况时：若nex[x] > nex[y] ，我们分配给 $x$ 更优

---

所有条件按照我分析的时候的先后顺序if else 判断即可，因为越往前优先级越大，后面只是有合并的可能性，而前面是直接已经可以合并了。

最后简单实现一下就行了

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#include <vector>
#include <unordered_map>
#include <queue>
#include <set>
using namespace std;
typedef long long ll;
typedef int itn;
const int N = 5e5 + 7, M = 6e6 + 7, mod = 1e9 + 7;
const ll INF = 1e18 + 7;

int n, m, t, k;
itn a[N], b[N];
vector<int> v[N];
int nex[N];

void solve()
{
    int ans = 0;
    scanf("%d", &n);
    for(int i = 1; i <= n; ++ i) {
        scanf("%d", &a[i]);
        v[a[i]].push_back(i);
    }
    for(int i = 1; i <= n; ++ i)
        nex[i] = n + 1;

    for(int i = 1; i <= n; ++ i) {
        for(int j = 0; j < (int)v[i].size() - 1; ++ j) {
            nex[v[i][j]] = v[i][j + 1];
        }
    }
    int x = 0, y = 0, nex_x = n + 1, nex_y = n + 1;
    for(int i = 1; i <= n; ++ i) {
        int z1 = a[i], z2 = a[i + 1];
        if(z1 == x) {
            nex_x = nex[i];
        }
        else if(z1 == y) {
            nex_y = nex[i];
        }
        else {
            ans ++ ;
            if(z2 == x && z2 != y) {
                y = z1;
                nex_y = nex[i];
            }
            else if(z2 == y && z2 != x) {
                x = z1;
                nex_x = nex[i];
            }
            else {
                if(nex_x < nex_y) {
                    y = z1;
                    nex_y = nex[i];
                }
                else {
                    x = z1;
                    nex_x = nex[i];
                }
            }
        }
    }
    printf("%d\n", ans);
}

int main()
{
    solve();
    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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75