POJ 3220 Jessica's Reading Problem

尺取法第三题，读题好烦……直接找了一个题解把中文意思拿来了。

感觉还是挺简单的，但是用了map费了点时间。500+ ms ，如果用hash估计可以降低很多……

题意：
给你一串序列，可能有很多相同元素，要你求最短的连续序列，使得这个序列包含整个序列中的所有元素。

思路：
set+map+尺取。因为数据范围在int内，开数组记录不实际，必须得用hash做，用map偷了个懒。

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

typedef long long ll;
const int inf = 0x3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;

int ary[maxn];

set<int> key;
map<int, int> num;

int main()
{
    int n;
    while (scanf("%d", &n) != EOF) {
        key.clear(), num.clear();
        each(i, n) scanf("%d", ary + i), key.insert(ary[i]);
        unsigned sz = key.size(), ans = inf;
        key.clear();
        for (int i = 0, j = 0; i < n; i++) {
            while (key.size() < sz && j < n) {
                num[ary[j]]++;
                key.insert(ary[j++]);
            }
            if (key.size() < sz)
                break;
            ans = min((unsigned)j - i, ans);
            if (--num[ary[i]] == 0)
                key.erase(ary[i]);
        }
        printf("%d\n", ans);
    }
    return 0;
}