POJ 3320 尺取法,Hash,map标记

时间:2021-08-18 01:30:48

1、POJ 3320

2、链接:http://poj.org/problem?id=3320

3、总结:尺取法,Hash,map标记

  看书复习,p页书,一页有一个知识点,连续看求最少多少页看完所有知识点

  必须说,STL够屌。。

#include<iostream>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
#include<cstdio>
#include<map>
using namespace std;
#define LL long long
#define INF 0x3f3f3f3f
const int N=;
int p,a[N];
map<int,int>n,x; int main()
{
while(~scanf("%d",&p))
{
for(int i=;i<=p;i++)
{
scanf("%d",&a[i]);
n[a[i]]++;
}
int s=n.size(); //记录总类别 int l=,r=,ans=INF;
while(true)
{
while((r<=p)&&(x.size()<s)){ //尺取法,要满足范围要求,否则右端点移动
x[a[r++]]++;
}
if(x.size()<s)break;
ans=min(ans,r-l);
x[a[l++]]--;
if(x[a[l-]]<=)x.erase(a[l-]); //关健点,在范围内这个类别数<=0,就删去 }
printf("%d\n",ans);
} return ;
}