【dog與lxy】8.25題解-necklace

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)過膳沽。

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


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


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


  4. 而在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;
}
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末揪胃,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子氛琢,更是在濱河造成了極大的恐慌喊递,老刑警劉巖,帶你破解...
    沈念sama閱讀 222,729評(píng)論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件阳似,死亡現(xiàn)場(chǎng)離奇詭異骚勘,居然都是意外死亡,警方通過查閱死者的電腦和手機(jī)撮奏,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,226評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門俏讹,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人畜吊,你說我怎么就攤上這事泽疆。” “怎么了玲献?”我有些...
    開封第一講書人閱讀 169,461評(píng)論 0 362
  • 文/不壞的土叔 我叫張陵殉疼,是天一觀的道長(zhǎng)。 經(jīng)常有香客問我捌年,道長(zhǎng)瓢娜,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 60,135評(píng)論 1 300
  • 正文 為了忘掉前任礼预,我火速辦了婚禮眠砾,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘托酸。我一直安慰自己褒颈,他們只是感情好柒巫,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,130評(píng)論 6 398
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著哈肖,像睡著了一般吻育。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上淤井,一...
    開封第一講書人閱讀 52,736評(píng)論 1 312
  • 那天布疼,我揣著相機(jī)與錄音,去河邊找鬼币狠。 笑死游两,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的漩绵。 我是一名探鬼主播贱案,決...
    沈念sama閱讀 41,179評(píng)論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼,長(zhǎng)吁一口氣:“原來是場(chǎng)噩夢(mèng)啊……” “哼止吐!你這毒婦竟也來了宝踪?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 40,124評(píng)論 0 277
  • 序言:老撾萬榮一對(duì)情侶失蹤碍扔,失蹤者是張志新(化名)和其女友劉穎瘩燥,沒想到半個(gè)月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體不同,經(jīng)...
    沈念sama閱讀 46,657評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡厉膀,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,723評(píng)論 3 342
  • 正文 我和宋清朗相戀三年,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了二拐。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片服鹅。...
    茶點(diǎn)故事閱讀 40,872評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖百新,靈堂內(nèi)的尸體忽然破棺而出企软,到底是詐尸還是另有隱情,我是刑警寧澤吟孙,帶...
    沈念sama閱讀 36,533評(píng)論 5 351
  • 正文 年R本政府宣布澜倦,位于F島的核電站,受9級(jí)特大地震影響杰妓,放射性物質(zhì)發(fā)生泄漏藻治。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,213評(píng)論 3 336
  • 文/蒙蒙 一巷挥、第九天 我趴在偏房一處隱蔽的房頂上張望桩卵。 院中可真熱鬧,春花似錦、人聲如沸雏节。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,700評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)钩乍。三九已至辞州,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間寥粹,已是汗流浹背变过。 一陣腳步聲響...
    開封第一講書人閱讀 33,819評(píng)論 1 274
  • 我被黑心中介騙來泰國(guó)打工, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留涝涤,地道東北人媚狰。 一個(gè)月前我還...
    沈念sama閱讀 49,304評(píng)論 3 379
  • 正文 我出身青樓,卻偏偏與公主長(zhǎng)得像阔拳,于是被迫代替她去往敵國(guó)和親崭孤。 傳聞我的和親對(duì)象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,876評(píng)論 2 361

推薦閱讀更多精彩內(nèi)容