necklace
題目描述
可憐的dog最終還是難逃厄運(yùn)约郁，被迫于lxy簽下城下之約己肮。這時(shí)候lxy開始刁難dog寓辱。
Lxy首先向dog炫耀起了自己的財(cái)富这敬，他拿出了一段很長(zhǎng)的項(xiàng)鏈缭保。這個(gè)項(xiàng)鏈由n個(gè)珠子按順序連在一起（1號(hào)珠子和n號(hào)珠子沒有相連）孕锄，每個(gè)珠子的顏色是1..m中的一種顏色(不妨用Ai表示第i個(gè)珠子的顏色)。
可dog當(dāng)然不肯服氣恬涧，于是他認(rèn)為一定可以找到一段長(zhǎng)度<=len的項(xiàng)鏈b1..blen(bi也是1..m中的一種顏色)啤月，沒有出現(xiàn)過。
出現(xiàn)過的定義就是存在一組C1..Cm滿足0<C1<C2<..<Cm<=n使得Aci=Bi。
然后lxy就要dog找出一段長(zhǎng)度<=len的項(xiàng)鏈沒有出現(xiàn)過十拣。這時(shí)候dog發(fā)現(xiàn)自己中計(jì)了捧杉，因?yàn)轫?xiàng)鏈太長(zhǎng)了而lxy規(guī)定的len卻很小忍坷。于是他又來找你求助了旬薯。不然的話，dog就要被迫簽下賣國(guó)條約了……..現(xiàn)在就請(qǐng)你幫dog沒有出現(xiàn)過的項(xiàng)鏈中最短的長(zhǎng)度趁猴。
輸入輸出
輸入文件：
第1行2個(gè)數(shù)n,m捕犬。接下來n行，每行一個(gè)數(shù)表示Ai。
輸出文件：
一個(gè)數(shù)，沒有出現(xiàn)過的項(xiàng)鏈中最短的長(zhǎng)度柬批。
樣例
輸入
2 3
1
2
輸出
1
說明
樣例解釋
B1=3沒有出現(xiàn)過楞艾，所以有長(zhǎng)度為1，顏色為3的項(xiàng)鏈滿足條件紧武。
數(shù)據(jù)范圍
100%的數(shù)據(jù)中，n<=500000,m<=100.
40%的數(shù)據(jù)中呛讲，n<=100,m<=3.
10%的數(shù)據(jù)中禾怠，n<=10,m<=2.
思路
給你一個(gè)長(zhǎng)度為N的序列A1..An。其中Ai的取值范圍[1,m]。要求一個(gè)最短長(zhǎng)度Len仿村，滿足存在一個(gè)序列長(zhǎng)度為L(zhǎng)en的B1..Blen焚志，這個(gè)序列在Ai中沒有出現(xiàn)過膳沽。
我們思考假設(shè)在從最左端開始的一段區(qū)間范圍內(nèi)堆缘，如果存在1~m中間的所有數(shù)字表箭，那么Len至少大于1盯桦。
假設(shè)緊跟這個(gè)區(qū)間之后又有一段數(shù)字包含了1~M。那么對(duì)于所有長(zhǎng)度為2的序列就都已經(jīng)存在渤刃，也就是Len要大于2拥峦。
以此類推，若整個(gè)Ai序列中以此有K個(gè)存在1~M的區(qū)間
- 而在k個(gè)1~M的區(qū)間之后卖子，已經(jīng)不會(huì)滿足存在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;
}
