POJ 3320 Jessica's Reading Problem （尺取法，时间复杂度O（n logn））

题目：

解法：定义左索引和右索引

　　1.先让右索引往右移，直到得到所有知识点为止；

　　2.然后让左索引向右移，直到刚刚能够得到所有知识点；

　　3.用右索引减去左索引更新答案，因为这是满足要求的子串。

　　4.不断重复1,2,3。直到搜索到最后，不论怎样都获得不了所有的知识点时跳出。

代码：

#include <iostream>

#include <algorithm>

#include <stdio.h>

#include <vector>

#include <map>

#include <set>

#include <queue>

using namespace std;

typedef long long ll;

#define INF 2147483647

int n;

int a[]; 

map <int,int> m;

int main(){

    int n;

    cin >> n;

    set <int> q;

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

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

        q.insert(a[i]);

//        cout << a[i] << endl;

    }

    int num = q.size();

//    cout << num << endl;

    int res = INF;

    int sum = ;

    int s = ;int t = ;

    while(true){

        while(t < n && sum != num){

            if(m[a[t]] == )

                sum++;

            m[a[t]]++;

            t++;

        }

        while(m[a[s]] > ){

            m[a[s]]--;

            s++;

            if(m[a[s-]] == ){

                sum--;

                break;

            }

        }

        if(sum < num-) break;

//        cout << s << " " << t << endl;

        res = min(res,t-s+);

    }

    cout << res << endl;

    return ;

}

巴特西

POJ 3320 Jessica's Reading Problem （尺取法，时间复杂度O（n logn））

最新文章

热门文章