necklace
题目描述
可怜的dog最终还是难逃厄运，被迫于lxy签下城下之约。这时候lxy开始刁难dog。
Lxy首先向dog炫耀起了自己的财富，他拿出了一段很长的项链。这个项链由n个珠子按顺序连在一起（1号珠子和n号珠子没有相连），每个珠子的颜色是1..m中的一种颜色(不妨用Ai表示第i个珠子的颜色)。
可dog当然不肯服气，于是他认为一定可以找到一段长度<=len的项链b1..blen(bi也是1..m中的一种颜色)，没有出现过。
出现过的定义就是存在一组C1..Cm满足0<C1<C2<..<Cm<=n使得Aci=Bi。
然后lxy就要dog找出一段长度<=len的项链没有出现过。这时候dog发现自己中计了，因为项链太长了而lxy规定的len却很小。于是他又来找你求助了。不然的话，dog就要被迫签下卖国条约了……..现在就请你帮dog没有出现过的项链中最短的长度。
输入输出
输入文件：
第1行2个数n,m。接下来n行，每行一个数表示Ai。
输出文件：
一个数，没有出现过的项链中最短的长度。
样例
输入
2 3
1
2
输出
1
说明
样例解释
B1=3没有出现过，所以有长度为1，颜色为3的项链满足条件。
数据范围
100%的数据中，n<=500000,m<=100.
40%的数据中，n<=100,m<=3.
10%的数据中，n<=10,m<=2.
思路
给你一个长度为N的序列A1..An。其中Ai的取值范围[1,m]。要求一个最短长度Len，满足存在一个序列长度为Len的B1..Blen，这个序列在Ai中没有出现过。
我们思考假设在从最左端开始的一段区间范围内，如果存在1~m中间的所有数字，那么Len至少大于1。
假设紧跟这个区间之后又有一段数字包含了1~M。那么对于所有长度为2的序列就都已经存在，也就是Len要大于2。
以此类推，若整个Ai序列中以此有K个存在1~M的区间
- 而在k个1~M的区间之后，已经不会满足存在1 ~M中间的所有数字，那么Ans=K+1。
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,ans;
int c[501000],h[500];
int main(){
freopen("necklace.in ","r",stdin);
freopen("necklace.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&c[i]);
int time=1,j=m;
for(int i=1;i<=n;i++)
if(h[c[i]]!=time){
h[c[i]]=time; j--;
if(j==0) {
ans++;time++;j=m;
}
}
printf("%d",ans+1);
return 0;
}
