AT_abc_397_c

题目大意：

将有

N

个数的数列分为两个连续子区间，求两个子区间中不同数的个最多有多少

思路：

我们用两个桶来记录数的个数，第一个桶记录左边，第二个桶记录右边，大于

1

记为重复，

0

记为空，默认在第一个数之前分割，把所有数都加入第二个桶，最后遍历每一个位置，将第

i

个数从右边移到左边，统计两个桶中不同数字的总个数个数，然后输出最大值。

AC code

CPP

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 1e6 + 10;

int n, ans, maxn;
int a[N], cnta[N], cntb[N];

signed main(){
	cin >> n;
	for(int i = 1 ; i <= n ; i ++) {
		cin >> a[i];
		cntb[a[i]] ++;
	}
	
	for(int i = 1 ; i <= n ; i ++) {
		if(cntb[i] > 0) ans ++;
	}
	
	for(int i = 1 ; i <= n ; i ++) {
		cntb[a[i]] --;
		if(cntb[a[i]] == 0) ans --;
		cnta[a[i]] ++;
		if(cnta[a[i]] == 1) ans ++;
		if(ans > maxn) maxn = ans;
	}
	
	cout << maxn << '\n';
	
	return 0;
}

题解：AT_abc397_c [ABC397C] Variety Split Easy

文章操作

AT_abc_397_c

题目大意：

思路：

AC code

相关推荐

评论

题解：AT_abc397_c [ABC397C] Variety Split Easy