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

传送门

题目大意

有n个数字，可以将他们分别放在两个数组中，数组元素的个数为合并相邻元素相同的值，比如

会变成

让两个数组长度尽量长

题解

贪心的选取，假如数组a的最后一个元素为x，数组b的最后一个元素为y，如果在原数组中x的下一个相同的数字在i，y的下一个相同的数字在j，i在j前面的话，就把数字放在b后面，分之把数字放在a后面

#include<cstdio>
const int MAX=1e5+5;
int a[MAX];
int loc[MAX],next[MAX];
int anum,bnum;
int ans;
int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	for(int i=0;i<=n;i++){
		loc[i]=n+1;
	}
	for(int i=n;i>=0;i--){
		next[i]=loc[a[i]];
		loc[a[i]]=i;
	}
	for(int i=1;i<=n;i++){
		if(a[anum]==a[bnum]){
			ans+=a[bnum]!=a[i];
			if(anum<bnum){
				anum=bnum;
			}
			bnum=i;
		}
		else if(a[anum]==a[i]){
			ans+=a[bnum]!=a[i];
			bnum=i;
		}else if(a[bnum]==a[i]){
			ans+=a[anum]!=a[i];
			anum=i;
		}else{
			if(next[anum]<next[bnum]){
				ans+=a[anum]!=a[i];
				anum=i;
			}else{
				ans+=a[bnum]!=a[i];
				bnum=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