题解：AT_abc397_c [ABC397C] Variety Split Easy

Q_ac · 2025-03-16 10:58:41 · 题解

AT_abc_397_c

题目大意：

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

思路：

我们用两个桶来记录数的个数，第一个桶记录左边，第二个桶记录右边，大于 1 记为重复， 0 记为空，默认在第一个数之前分割，把所有数都加入第二个桶，最后遍历每一个位置，将第 i 个数从右边移到左边，统计两个桶中不同数字的总个数个数，然后输出最大值。

AC code

#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;
}