#P3064. [USACO12DEC] Gangs of Istanbull/Cowstantinople G

[USACO12DEC] Gangs of Istanbull/Cowstantinople G

题目描述

农场生活很艰难,而生活艰难时,你就必须变得强硬。奶牛们组成了帮派(方便起见,编号为 11MM)。起初,这些帮派和平共处了一段时间,但现在情况真的失控了!

奶牛们正在争夺一块大牧场的控制权。这场冲突持续若干分钟。每一分钟,都有一头奶牛走进牧场。

  • 如果牧场是空的,那么这头新来的奶牛所属的帮派就被视为控制了牧场。
  • 如果牧场已经被这头新来的奶牛所属的帮派控制,那么这头奶牛就直接开始吃草。
  • 否则,一头正在牧场吃草的、来自当前控制帮派的奶牛会与这头新来的奶牛对峙。

两头奶牛之间的对峙会从一些争吵开始,但最终它们总会意识到彼此之间的相似之处远多于差异。于是,这两头奶牛幡然醒悟,离开各自的帮派和牧场,去 FJ 的酒馆喝一杯冰镇豆奶。如果这次对峙后牧场空了,那么就没有帮派控制牧场。

Bessie 预见到了这些对峙将如何发生。她知道每个帮派有多少头奶牛。Bessie 非常希望她的帮派(编号为 11)在冲突结束后,所有奶牛要么在牧场要么在酒馆后,能够控制牧场。请你帮助 Bessie 判断她的帮派是否有可能在最后控制牧场。

如果可能,Bessie 还想知道最后她的帮派最多能有多少头奶牛留在牧场上。输出这个数字,以及能达到这个数字的字典序最小的奶牛入场顺序。如果存在某个位置kk,使得 Xk<YkX_k < Y_k 且对于所有 i<ki < kXi=YiX_i = Y_i,则称顺序 XX 的字典序小于顺序 YY

输入格式

  • 11 行:两个整数 NN (1N1001 \le N \le 100) 和 MM (1MN1 \le M \le N),用一个空格隔开。NN 是所有帮派奶牛的总数。MM 是帮派的总数。
  • 22 行到第 1+M1 + M 行:第 1+i1 + i 行表示帮派 ii 有多少成员。每个帮派至少有 11 名成员。

输出格式

  • 11 行:如果 Bessie 的帮派在冲突结束后能控制牧场,则在一行中输出 YES。否则输出 NO
  • 22 行:如果 Bessie 的帮派能控制牧场,则在一行中输出能留在牧场上的最大奶牛数量。
  • 33 行到第 2+N2 + N 行:在第 i+2i + 2 行,输出在第 ii 分钟出现的奶牛所属帮派的编号,这个顺序是能达到上述最大数量且字典序最小的顺序。
5 3 
2 
1 
2 

YES 
1 
1 
3 
2 
3 
1 

提示

【样例解释】
共有 55 头奶牛和 33 个帮派。Bessie 的帮派(帮派 11)有 22 名成员,帮派 2211 名成员,帮派 3322 名成员。


只有一头来自 Bessie 帮派的奶牛最终能留在牧场上。

由 DeepSeekV3 翻译。