codeforces 1480 D1 Painting the Array I (贪心)_d1. painting the array

题面

题意

把一个长度为n的数组分成两个子数组a，b，要求seg(a)+seg(b) 最大 ，seg（a）表示数组中不同的连续段，例如[1,1,2,2,3,3,3,1] 连续段就是[1,2,3,1] 长度是4

题解

1. 我们采用贪心的思想考虑，假设v1是数组a的末尾元素，v2是数组b的末尾元素，我们依次遍历原数组中的元素，然后考虑放在a后还是b后是最优解
2. 如果v1==v2 ,a[i]放在哪里都一样，贡献值是0/1 ，如果v1 != v2, 如果是v1 == a[i] , a[i]放在v1后贡献值是0，放在v2后的贡献值是1，贪心考虑局部最优解，肯定就是放在v2后边了，然后更新v2，v1!=a[i] ,v2 == a[i] 也是一样的道理
3. 还有一种情况就是v1，v2，a[i] 都不相同 ，那么a[i] 是否可以任意放，肯定是不行的，我们举个例子，假设现在v1=1,v2=2,剩余数组[3,2,2] ,那么3就不能随便放，因为3如果放在1后边，接下来第二个2放在哪里贡献值都为0，对于这种情况，我们就要看下一个1出现的位置和下一个2出现的位置，显然2出现的位置要更早一些，那么3就应该放在2后边来防止相同的数字出现减小贡献值具体看代码

代码

#include<bits/stdc++.h>

using namespace std;
const int N = 2e5 + 10;

int n, a[N], id[N];
vector<int> v[N];

int main() {

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        v[a[i]].push_back(i);
    }
    int res = 0;
    int v1 = -1, v2 = -1;
    for (int i = 1; i <= n; i++) {
        id[a[i]]++;
        if (v1 == v2) {
            if (v1 != a[i]) {
                v1 = a[i];
                res++;
            }
        } else if (v1 == a[i] && v2 != a[i]) {
            v2 = a[i];
            res++;
        } else if (v1 != a[i] && v2 == a[i]) {
            v1 = a[i];
            res++;
        } else {
            if (v1 == -1) v2 = a[i], res++;
            else if (v2 == -1) v1 = a[i], res++;
            else {
                int next_v1 = n + 1, next_v2 = n + 1;
                if (id[v1] < v[v1].size()) next_v1 = v[v1][id[v1]];
                if (id[v2] < v[v2].size()) next_v2 = v[v2][id[v2]];
                if (next_v1 < next_v2) v1 = a[i], res++;
                else v2 = a[i], res++;
            }
        }

    }
    cout << res << endl;

    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