農場上的生活是艱苦的,而當生活變得艱苦時,乳牛們也必須變得堅強。
農場上的牛組成了一些幫派(以編號 $1, 2, \dots, M$表示)。
這些幫派和平共處了一段時間,但現在狀況逐漸失去控制了!
牛隻們正在爭奪一大片草地的控制權。這些衝突發生在連續的若干分鐘內,每一分鐘,一隻牛會走進這片草地。如果此時草地上沒有任何牛,那麼這隻新進去的牛所在的幫派就能佔領這片草地。如果這片草地已經被該隻牛所屬的幫派佔領了,那麼這隻牛就只是在這片草地吃草。否則,原本佔領這片草地的幫派將會派出一隻牛與新進的牛發生衝突。
這些衝突由吵架開始,然後兩隻牛將會發現他們相同之處比不同之處更多,當兩隻牛發現他們各自的錯誤後,就離開他們所在的幫派,走出草地,再去Farmer John的客棧裡喝杯冰牛奶。如果在某次衝突之後,這片草地上沒有任何牛,那麼沒有一個幫派被視為佔領了這片草地。
Bessie關心這些衝突發生的情況。他知道每一個幫派有幾隻乳牛。
在所有衝突發生完後,每隻牛要嘛在那片草地上,要嘛在Farmer John的客棧裡喝牛奶,
Bessie希望此時的草地是被他所在的幫派佔領。請你幫助Bessie判斷她所在的幫派(編號為1)是否有可能在最後佔領這片草地。
如果有可能,Bessie想知道最後最多能有多少隻牛仍然屬於她所在的幫派。
請輸出這個數字,以及字典序最小的方案。
一個方案是一個幫派編號的序列 $p$,表示走進草地的牛隻幫派編號依序是 $p_1, p_2, \dots, p_n$ 。
第一行包含以空白隔開的兩個數字 $N, M$ ,分別表示牛隻的總數量,以及總共有幾個幫派。
接下來 $M$ 行各有一個正整數,分別表示每個幫派的牛隻數量。
$1 \leq M \leq N$
$1 \leq N \leq 200000$
注意:與原題$N$的上限不同
如果Bessie的幫派最後不可能佔領這片草地,你只需要輸出一個 NO
。
否則,輸出 YES
,並在下一行輸出最後最多在草地上可以留下多少牛隻
接下來以換行的格式輸出字典序最小的讓牛隻走進草地的順序,見範測。
From USACO 2012 Dec. Gangs
Notice the constraint.
testdata set by Omelet
如果測資有誤請通知我QQ
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~19 | $M \leq N \leq 100$ | 1 |
2 | 0~24 | $M \leq N \leq 3000$ | 1 |
3 | 0~19, 25~29 | $M \leq N; N \leq 200000; M \leq 100$ | 1 |
4 | 0~34 | $M \leq N; N \leq 200000; M \leq 3000$ | 1 |
5 | 0~49 | $M \leq N \leq 200000$ | 1 |