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