UVA11572 唯一的雪花

发表于

UVA11572 唯一的雪花 Unique Snowflakes

题目描述

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

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

输入格式

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

输出格式

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

输入输出样例 #1

输入 #1

1
2
3
4
5
6
7
1
5
1
2
3
2
1

输出 #1

1
3

思路分析 + 代码实现

相当于求一个序列的一个最长子序列，使得没有重复数字。注意到数据范围最大为 $Tn$ （虽然时限2秒），说明需要一个 $\operatorname{O}(n)$ 或者 $\operatorname{O}(n\log n)$ 的算法。那么选择用双指针法，先固定 $l = 0$ ，然后让 $r$ 递增，直至出现重复，此时更新答案，然后令 $l$ 自增，删掉区间最左边的数（即引起重复的数）。不断重复上述过程，得到答案。

那么怎么高效记录数字是否重复呢？用 map、set 或者用哈希？但这无疑使得时间复杂度大大增加。直接使用布尔数组标记的话，则需要用 $10^9 \div 1024^2 \approx 954 MB$ 。因此我们用 bitset ，内存开销降低为原来的 $\frac{1}{8}$ 。要注意内层 while 循环的循环条件为 $l$ < $n$ ，这是为了重置 $vis$ 数组，保证在下一组测试用例时初始化正确，代码如下：

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
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e9 + 1, MAXM = 1e6 + 1;
int nums[MAXM];
int T, n, l, r, ans;
bitset<MAXN> vis;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> T;
    while (T--) {
        cin >> n;
        l = r = ans =0;
        if (n <= 0) continue;
        for(int i = 0; i < n; i++)
            cin >> nums[i];
        while (l < n) { // 注意
            while (r < n && !vis[nums[r]])
                vis.set(nums[r++]);
            ans = max(ans, r - l);
            vis.reset(nums[l++]);
        }
        cout << ans << "\n";
    }
    return 0;
}