POJ3320 Jessica's Reading Problem(尺取+map+set）

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

POJ3320 Jessica's Reading Problem

set用来统计所有不重复的知识点的数，map用来维护区间[s,t]上每个知识点出现的次数，此题很好的体现了map的灵活应用

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <queue>

#include <vector>

#include <map>

#include <set>

#include <string>

#include <cmath>

using namespace std;

const int INF = 0x3f3f3f3f;

typedef long long ll;

const int MAX_P = ;

int P;

int a[MAX_P];

int main()

{

    scanf("%d", &P);

    for (int i = ; i < P; ++i)

    {

        scanf("%d", &a[i]);

    }

    set <int> all;

    for (int i = ; i < P; ++i) {

        all.insert(a[i]);

    }

    int n = all.size();

    int s = , t = , num = ;

    map<int, int> count;

    int res = P;

    for (;;)

    {

        while (t < P && num < n) {

            if (count[a[t]]== ) { //出现了新的知识点

                num++;

            }

            count[a[t]]++;

            t++;

        }

        if (num < n) break;

        res = min(res, t-s);//更新最小区间长度

        count[a[s]]--;

        if (count[a[s]] == ) //某个知识点出现次数为0

        {

            num--;

        }

        s++;

    }

    printf("%d\n", res );

    return ;

}