a344: 分配小珠
Tags :
Accepted rate : 22人/27人 ( 81% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-05-03 14:22

Content

你正在參加一個有獎比賽,比賽的進行方式如下: 現有 N 粒編號由 1 至 N 的小珠及 T 條直徑與小珠相若的直立玻璃管。 小珠原本放在一個盒子內。首先,你從盒子內抽 T 粒小珠,分別放在 T 條管內,每條管放一粒。 然後再從盒子內一粒一粒珠的抽出,每抽一粒珠後就要把它放在其中一條管內, 要求是管內原來最頂的一粒珠的編號必定要小於將要放入去的珠的編號。 若有多條管合符這個要求,你可以選擇任一條管來放。 若按這個要求去做,任何時一條管內的珠的編號由下而上必定是遞增的。

   
   
  
  

假設管的長度足以放入任意多粒珠。要得獎你就要把 N 粒珠在不破壞順序要求的情況下全部放入玻璃管內。 上圖顯示三條管的情況。到目前為止,珠的在管內的順序都是正確的。 但很明顯,你這次的嘗試是失敗了。因在目前的情況下,在你抽到 2 號珠時, 你就沒法把它放入任何一條管內。

由放你沒有使用任何策略,所以你玩了幾次後,發覺每次都不成功。 你不甘心失敗,於是記下了你每次你抽珠的編號的順序。回家後你問你的 AI 電腦在該順序下到底是否可以把全部 N 粒珠都放入管內。

Input

輸入數據中有若干組數列,每組數列的格式如下: 第一行上有兩個正整數 N T ,分別代表小珠及玻璃管的數目。(1 ≤ N ≤ 100,000 及 1 ≤ T ≤ 1,000 且 T < N) 隨後的一行上有 N 個整數,每個數字之間以一個空格分開,這些數字代表抽出珠子編號順序。 這裏最先抽出的 T 粒珠是要分別放到 T 條玻璃管內,每條放一粒。隨後抽出的粒就可以按需要放到某一條特定的管內。

最後一組輸入只有一個 0,代表輸入的終結。

Output

對應於每組輸入數據,輸出為 YES 若有方法可以把所有粒都放入管內,反之則輸出 NO。

Sample Input #1
3 2
3 1 2
5 2
5 4 3 2 1
4 3
3 2 1 4
0
Sample Output #1
YES
NO
YES
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (33%): 1.0s , <1K
公開 測資點#1 (33%): 1.0s , <1K
公開 測資點#2 (34%): 1.0s , <1M
Hint :

#非官方測試數據

Tags:
出處:
MOI 2020 [管理者:
ricky (電腦黃)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」