题目链接

题目描述

企业家 Emily 有一个很酷的主意：把雪花包起来卖。她发明了一台机器，这台机器可以捕捉飘落的雪花，并把它们一片一片打包进一个包裹里。一旦这个包裹满了，它就会被封上送去发售。

Emily 的公司的口号是“把独特打包起来”，为了实现这一诺言，一个包裹里不能有两片一样的雪花。不幸的是，这并不容易做到，因为实际上通过机器的雪花中有很多是相同的。Emily 想知道这样一个不包含两片一样的雪花的包裹最大能有多大，她可以在任何时候启动机器，但是一旦机器启动了，直到包裹被封上为止，所有通过机器的雪花都必须被打包进这个包裹里，当然，包裹可以在任何时候被封上。

输入格式

第一行是测试数据组数 $T$，对于每一组数据，第一行是通过机器的雪花总数 $n$（$n \le {10}^6$），下面 $n$ 行每行一个在 $[0, {10}^9]$ 内的整数，标记了这片雪花，当两片雪花标记相同时，这两片雪花是一样的。

输出格式

对于每一组数据，输出最大包裹的大小。

题解

模拟一个滑动窗口的左端、右端，通过去重取均不重复区间的长度最大值

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int t, n, a[N];
map<int, int> cnt;
int main() {
    cin >> t;
    while (t--) {
        int ans = 1;
        cnt.clear();
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        int l = 1, r = 1, rep = 0;
        cnt[a[1]] = 1;
        while (l <= r && r <= n) {
            if (rep == 0) {
                ans = max(ans, r - l + 1);
                r++;
                cnt[a[r]]++;
                if (cnt[a[r]] > 1)
                    rep++;
            } else {
                cnt[a[l]]--;
                if (cnt[a[l]] == 1)
                    rep--;
                l++;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

注意

1. 多测记得换行