专栏首页饶文津的专栏【POJ 3320】Jessica's Reading Problemc(尺取法)

【POJ 3320】Jessica's Reading Problemc(尺取法)

题意

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 <cstdio>
#include <map>
using namespace std;

map <int,int> 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<p && r<p)
    {
        if (v[d[r]]==0)
        {
            cnt++;
        }

        v[d[r]]++;
        r++;

        while (v[d[l]]>1)
        {
            v[d[l]]--;
            l++;
        }
        if (cnt==n && r-l < ans)
        {
            ans=r-l;
        }
    }
    printf("%d",ans);
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【USACO 1.3】Ski Course Design

    n个点(n<=1000)大小范围[0,100],改变一些点的值,使得极差不超过17,代价为改变值的平方。

    饶文津
  • 「c++小学期」实验题目及代码

    面向对象编程的C++,和平时做题用的C++还是有差距的。实验的题目都是小题目,就都做一下吧。

    饶文津
  • 【Codeforces 723C】Polycarp at the Radio 贪心

    n个数,用最少的次数来改变数字,使得1到m出现的次数的最小值最大。输出最小值和改变次数以及改变后的数组。

    饶文津
  • 【2020HBU天梯赛训练】7-40 列车调度

    两端分别是一条入口(Entrance)轨道和一条出口(Exit)轨道,它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入,最后从出口离开。在图中有...

    韩旭051
  • HDU5972Regular Number(ShiftAnd算法 bitset)

    接下来\(n\)行,每行开头有一个整数\(num\)表示匹配串中该位置的字符可以在\(num\)个桅子花出现,接下来输入这\(num\)个位置

    attack
  • UVA Machined Surfaces

    题意:这道题我读了很久,也没有读懂最后看的解体报告才懂得题意,题目不难,但是还是错了两次,几个字符窜,左边的‘x’向右边移动当和右边的‘x’连接时候,求剩下的字...

    用户1624346
  • 【LeetCode第 177 场周赛】5171. 最接近的因数

    两数乘积等于 num + 1 或 num + 2 以绝对差进行度量,两数大小最接近 你可以按任意顺序返回这两个整数。

    韩旭051
  • 2018年全国多校算法寒假训练营练习比赛(第一场)六子冲

     棋盘上攻击方的2个棋子(2子必须相连并主动移动其中的1个)与被攻方的1个棋子皆处在一条直线上并相邻时,被攻方的这个棋子就被消灭  每次移动后判断一下,移动后...

    mathor
  • P2375 动物园

    题目描述 近日,园长发现动物园中好吃懒做的动物越来越多了。例如企鹅,只会卖萌向游客要吃的。为了整治动物园的不良风气,让动物们凭自己的真才实学向游客要吃的,园长决...

    attack
  • LeetCode 201. 数字范围按位与(位运算)

    给定范围 [m, n],其中 0 <= m <= n <= 2147483647,返回此范围内所有数字的按位与(包含 m, n 两端点)。

    Michael阿明

扫码关注云+社区

领取腾讯云代金券