Codeforces Round #700 (Div. 2)D1 - Painting the Array I_codeforces painting the array i

传送门
一、题意： 将数组a分为0和1两个部分，分类完后需要分别将相邻的相同元素合并，合并后统计个数相加，要求总和达到最大值。
二、思路： 可以开两个栈s1,s2，正常分类方法就是s1放一个然后s2放一个，如果遇到跟栈顶相同的就要特判然后放到另外一个栈中。
但是还有一种情况要注意:可能a[i]与s1的栈顶不同但是a[i+1],a[i+2]与s1的栈顶相同，但是根据上面的轮换规则该轮应将a[i]放在s2中，如果这样做可能会导致a[i+1]与s1栈顶合并，就会导致种类减少，所以需要特判。
cpp代码

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<vector>
#include<queue>
#include<stack>
#include<string>
#include<set>
#include<cmath>
#include<map>
#define ll long long
using namespace std;
const int MAXN = 100005;
int a[MAXN];
stack<int>s1, s2;
int main()
{
	//std::ios::sync_with_stdio(0);
	int n;
	scanf("%d", &n);
	int flag = 1;
	for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
	for (int i = 1; i <= n; i++) {
		if (s1.empty())s1.push(a[i]);
		else if (flag) {
			if (!s2.empty()&&a[i] == s2.top())s1.push(a[i]);
			else {
				if (a[i + 1] == s1.top())s1.push(a[i]);
				else {
					s2.push(a[i]);
					flag = 0;
				}
			}
		}
		else {
			if (!s1.empty()&&a[i] == s1.top())s2.push(a[i]);
			else {
				if (a[i + 1] == s2.top())s2.push(a[i]);
				else {
					s1.push(a[i]);
					flag = 1;
				}
			}
		}
	}
	int x = 0, next = 0;
	flag = 1;
	ll ans = 0;
	while (!s1.empty()) {
		x = s1.top();
		s1.pop();
		if (flag) {
			ans++;
			flag = 0;
		}
		else if (x != next)ans++;
		next = x;
	}
	flag = 1, next = 0;
	while (!s2.empty()) {
		x = s2.top();
		s2.pop();
		if (flag) {
			ans++;
			flag = 0;
		}
		else if (x != next)ans++;
		next = x;
	}
	printf("%lld", 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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74