POJ 3320 Jessica's Reading Problem

Description

求覆盖数组中出现过的所有元素的最小的区间长度（连续）

Idea

满足尺取条件：

1. 连续
2. 若设s -> t， 则s+1 -> ? ? >= t

Code

#include <set>
#include <map>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
int a[1000005];

int Scan()
{
    int res = 0, ch, flag = 0;
    if((ch = getchar()) == '-')
        flag = 1;
    else if(ch >= '0' && ch <= '9')
        res += ch - '0';
    while((ch = getchar()) >= '0' && ch <= '9')
        res = res * 10 + ch - '0';
    return flag ? -res : res;
}

int main()
{
    int n, t, sz;
    scanf("%d", &n);
    getchar();
    set<int> st;
    for(int i = 0; i < n; ++i)
    {
        a[i] = Scan();
//scanf("%d", &a[i]);
        st.insert(a[i]);
    }
    sz = st.size();
    st.clear();
    int res = n, l = 0, r = 0, num = 0;
    map<int, int> mp;
    while(1)
    {
        while(r < n && num < sz)
        {
            if(mp[a[r]] == 0)
                num++;
            mp[a[r]]++;
            r++;///if this sentence is put at the head.a[0] is lost!
        }
        if(num < sz)
            break;
        else
        {
            res = min(res, r - l);
            mp[a[l]]--;
            if(mp[a[l]] == 0)
                num--;
            l++;
        }
    }
    cout << res << '\n';
    return 0;
}

注意res初始化的值