Justoj 2388最短区间 贪心

时间：2024-01-21 15:26:03

2388: 最短区间

Time Limit: 1 s      Memory Limit: 128 MB

Submit My Status

Problem Description

有M种不同颜色的气球(颜色从1至M表示)，现在有一排N个位置，需要往这N个位置中填充一些气球，可填也可不填。求最短的区间长度使的这个区间中包含M种颜色的气球。如果没有则输入-1.

Input

第一行输入N和M，N表示位置长度，M表示气球颜色数量。(1≤M≤1000，1≤N≤106)(1≤M≤1000，1≤N≤106)。

第二行输入N个数，第i个数ai表示第i个位置气球的颜色，0表示没填充气球。(0≤ai≤M)(0≤ai≤M)

Output

输出符合要求的最短区间长度，没有则输入-1。

Sample Input

10 6

1 2 3 4 6 3 0 1 2 5

Sample Output

7

题解：用数组p记录颜色，数组cnt记录各颜色出现次数，x代表所取区段的头部，num记录颜色种类，当遍历到头部颜色出现两次，头部往后移动直至该头部颜色只出现一次（目的就是不改变颜色种类的前提下通过移动头部缩短区间长度），每次遍历判断一下颜色种类是否达到，达到则取最短区间长度。

#include<iostream>

#define ll long long

using namespace std;

ll p[1000011],cnt[1011];

int main()

{

        ll n,m,x,mn,num;

        scanf("%lld %lld",&n,&m);

        x=0;mn=9999999999;num=0;

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

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

                if(!p[i])//0

                        continue;

                if(!cnt[p[i]])//未出现过的颜色

                        num++;

                cnt[p[i]]++;//该颜色出现次数+1

                while(!p[x]||cnt[p[x]]>1){//出现与头部相同的颜色或者头部为0，头部往后推1位

                        cnt[p[x]]--;

                        x++;

                }

                if(num==m)//

                        mn=min(mn,i-x+1);

        }

        printf("%d\n",num==m?mn:-1);

        return 0;

}

相关文章