【POJ 3320】Jessica's Reading Problemc（尺取法）-白红宇

【POJ 3320】Jessica's Reading Problemc（尺取法）

阅读量：6893 次

发布时间：2019-06-27

本文共 708 字，大约阅读时间需要 2 分钟。

题意

P个数，求最短的一段包含P个数里所有出现过的数的区间。

分析

　　尺取法，边读边记录每个数出现次数num[d[i]]，和不同数字个数n个。

　　尺取时，l和r 代表区间两边，每次r++时，d[r]即r的出现次数+1，d[l]即l的出现次数大于1时，左边可以短一点，d[l]--，l++，直到d[l]出现次数为1，当不同数达到n个，且区间更小，就更新答案。

代码

#include 
     
      #include 
      using namespace std;map 
       
         num,v;int p,l,r,n,cnt;int d[1000005];int ans=9999999;int main(){    scanf("%d", &p);    for (int i = 0; i < p; i++)    {        scanf("%d",&d[i]);        if (num[d[i]]==0)        {            n++;        }        num[d[i]]++;    }    l=0;    r=0;    while(l
        1)        {            v[d[l]]--;            l++;        }        if (cnt==n && r-l < ans)        {            ans=r-l;        }    }    printf("%d",ans);    return 0;}

转载地址：http://jpzdl.baihongyu.com/

你可能感兴趣的文章