题解：AT_abc397_c [ABC397C] Variety Split Easy

题目大意：

有

n

个数，将这

n

个数分成两段连续的子序列，求这两个子序列中不同元素数量的最大值。

因为是求不同元素的数量，所以我们要去重。而众所周知，有一个叫

set

的东西，能自动去重。但是，我们不能把整个数列一起塞进

set

里，因为两个子序列中可能分别有两个相同的数，要算入各自的答案里。于是，易想到开两个

set

。一个存左子序列的答案，一个存右子序列的答案。最后把

1

到

n

的左右答案加起来求

max

就可以了。

代码如下：

CPP

#include <bits/stdc++.h>

using namespace std;
int n;
int a[300010];
int l[300010], r[300010];
set<int> sl, sr;

int main(){
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++){
        sl.insert(a[i]);
        l[i] = sl.size();
    }
    for (int i = n; i >= 1; i--){//注意要从大到小循环
        sr.insert(a[i]);
        r[i] = sr.size();
    }
    int ans = 0;
    for (int i = 1; i < n; i++){
        int sum = l[i] + r[i + 1];//左答案是1 -- i，右答案是i + 1 -- n
        ans = max(ans, sum);
    }
    cout << ans;
    return 0;
}

题解：AT_abc397_c [ABC397C] Variety Split Easy

文章操作

题目大意：

相关推荐

评论

题解：AT_abc397_c [ABC397C] Variety Split Easy