#P3064. [USACO12DEC] Gangs of Istanbull/Cowstantinople G
[USACO12DEC] Gangs of Istanbull/Cowstantinople G
题目描述
农场生活很艰难,而生活艰难时,你就必须变得强硬。奶牛们组成了帮派(方便起见,编号为 到 )。起初,这些帮派和平共处了一段时间,但现在情况真的失控了!
奶牛们正在争夺一块大牧场的控制权。这场冲突持续若干分钟。每一分钟,都有一头奶牛走进牧场。
- 如果牧场是空的,那么这头新来的奶牛所属的帮派就被视为控制了牧场。
- 如果牧场已经被这头新来的奶牛所属的帮派控制,那么这头奶牛就直接开始吃草。
- 否则,一头正在牧场吃草的、来自当前控制帮派的奶牛会与这头新来的奶牛对峙。
两头奶牛之间的对峙会从一些争吵开始,但最终它们总会意识到彼此之间的相似之处远多于差异。于是,这两头奶牛幡然醒悟,离开各自的帮派和牧场,去 FJ 的酒馆喝一杯冰镇豆奶。如果这次对峙后牧场空了,那么就没有帮派控制牧场。
Bessie 预见到了这些对峙将如何发生。她知道每个帮派有多少头奶牛。Bessie 非常希望她的帮派(编号为 )在冲突结束后,所有奶牛要么在牧场要么在酒馆后,能够控制牧场。请你帮助 Bessie 判断她的帮派是否有可能在最后控制牧场。
如果可能,Bessie 还想知道最后她的帮派最多能有多少头奶牛留在牧场上。输出这个数字,以及能达到这个数字的字典序最小的奶牛入场顺序。如果存在某个位置,使得 且对于所有 有 ,则称顺序 的字典序小于顺序 。
输入格式
- 第 行:两个整数 () 和 (),用一个空格隔开。 是所有帮派奶牛的总数。 是帮派的总数。
- 第 行到第 行:第 行表示帮派 有多少成员。每个帮派至少有 名成员。
输出格式
- 第 行:如果 Bessie 的帮派在冲突结束后能控制牧场,则在一行中输出
YES。否则输出NO。 - 第 行:如果 Bessie 的帮派能控制牧场,则在一行中输出能留在牧场上的最大奶牛数量。
- 第 行到第 行:在第 行,输出在第 分钟出现的奶牛所属帮派的编号,这个顺序是能达到上述最大数量且字典序最小的顺序。
5 3
2
1
2
YES
1
1
3
2
3
1
提示
【样例解释】
共有 头奶牛和 个帮派。Bessie 的帮派(帮派 )有 名成员,帮派 有 名成员,帮派 有 名成员。
只有一头来自 Bessie 帮派的奶牛最终能留在牧场上。
由 DeepSeekV3 翻译。