Codeforces Round #700 (Div. 2)D1. Painting the Array I

题面

官方题解

题解大意

约定: + 我们将生成的两个序列分别称为s和t, 也就是a⁽⁰⁾和a⁽¹⁾ + 我们将s和t的最后一个元素分别称为x和y + 我们将扫描a_i过程中的当前元素称为z + 我们将x在z后首次出现的位置称为next(x)

贪心策略I: + z 等于 x 或 y 中某一个, 将 z 分配给相反的子序列, 比如 z == x 时, 将 z 分配给 t 附加在 y 后. 特别的, 如果 z == x == y 时, 任意分配即可

贪心策略II: + 如果 z, x, y 互不相等, 将 z 分配给具有最近的下一个相同值的值后. 说人话就是: 如果 next(x) < next(y), 则 z 附加在 x 后, 否则, z 附加在 y 后

证明: 见官方题解

一点点改动

首先, 题目并没有要求输出子序列, 所以重复元素就不需要操作了, z == x == y 时, 跳过即可

其次, 影响结果的是两个元素之间的关系, 所以不需要求next(x)和next(y)(~~TLE警告~~)了, 考虑 a_{i +
1}就可以了

完整AC代码

这里其实并不需要用vector, 因为我们只考虑尾部元素, 既然AC了, 优化的事情就交给读者了.

点我查看完整代码

#include<algorithm>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<map> 
#include<string>
#include<vector>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 9;
const int INF = 1e9;
int a[maxn] = {0};
vector<int> a0, a1;
int main(){
    int n;
    scanf("%d ", &n);
    int ans = 0;
    a0.push_back(0);
    a1.push_back(0);
    for (int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
    }
    for (int i = 1; i <= n; i++){
        if (a[i] == a0.back()){
            if (a[i] != a1.back()){
                a1.push_back(a[i]);
            }
        }
        else if (a[i] == a1.back()){
            if (a[i] != a0.back()){
                a0.push_back(a[i]);
            }
        }
        else{
            if (a0.back() == a1.back()){
                a0.push_back(a[i]);
                continue;
            }
            if (a[i + 1] == a1.back()){
                a1.push_back(a[i]);
            }
            else{
                a0.push_back(a[i]);
            }
        } 
    }
    ans = a0.size() + a1.size() - 2;
    printf("%d", ans);
    return 0;
}