necklace

題目描述

可憐的dog最終還是難逃厄運，被迫于lxy簽下城下之約。這時候lxy開始刁難dog。
Lxy首先向dog炫耀起了自己的財富，他拿出了一段很長的項鏈。這個項鏈由n個珠子按順序連在一起（1號珠子和n號珠子沒有相連），每個珠子的顏色是1..m中的一種顏色(不妨用Ai表示第i個珠子的顏色)。
可dog當(dāng)然不肯服氣，于是他認為一定可以找到一段長度<=len的項鏈b1..blen(bi也是1..m中的一種顏色)，沒有出現(xiàn)過。
出現(xiàn)過的定義就是存在一組C1..Cm滿足0<C1<C2<..<Cm<=n使得Aci=Bi。
然后lxy就要dog找出一段長度<=len的項鏈沒有出現(xiàn)過。這時候dog發(fā)現(xiàn)自己中計了，因為項鏈太長了而lxy規(guī)定的len卻很小。于是他又來找你求助了。不然的話，dog就要被迫簽下賣國條約了……..現(xiàn)在就請你幫dog沒有出現(xiàn)過的項鏈中最短的長度。

輸入輸出

輸入文件：
第1行2個數(shù)n,m。接下來n行，每行一個數(shù)表示Ai。

輸出文件：
一個數(shù)，沒有出現(xiàn)過的項鏈中最短的長度。

樣例

輸入

2 3
1
2

輸出

1

說明

樣例解釋
B1=3沒有出現(xiàn)過，所以有長度為1，顏色為3的項鏈滿足條件。

數(shù)據(jù)范圍

100%的數(shù)據(jù)中，n<=500000,m<=100.
40%的數(shù)據(jù)中，n<=100,m<=3.
10%的數(shù)據(jù)中，n<=10,m<=2.

思路

給你一個長度為N的序列A1..An。其中Ai的取值范圍[1,m]。要求一個最短長度Len，滿足存在一個序列長度為Len的B1..Blen，這個序列在Ai中沒有出現(xiàn)過。

1. 我們思考假設(shè)在從最左端開始的一段區(qū)間范圍內(nèi)，如果存在1~m中間的所有數(shù)字，那么Len至少大于1。

   
   

2. 假設(shè)緊跟這個區(qū)間之后又有一段數(shù)字包含了1~M。那么對于所有長度為2的序列就都已經(jīng)存在，也就是Len要大于2。

   
   

3. 以此類推，若整個Ai序列中以此有K個存在1~M的區(qū)間

   
   
4. 而在k個1~M的區(qū)間之后，已經(jīng)不會滿足存在1 ~M中間的所有數(shù)字，那么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;
}