P8095 [USACO22JAN] Cereal 2 S
题目描述
Farmer John 的奶牛们的早餐最爱当然是麦片了!事实上,奶牛们的胃口是如此之大,每头奶牛一顿饭可以吃掉整整一箱麦片。
最近农场收到了一份快递,内有 $M$ 种不同种类的麦片($2\le M\le 10^5$)。不幸的是,每种麦片只有一箱!$N$ 头奶牛($1\le N\le 10^5$)中的每头都有她最爱的麦片和第二喜爱的麦片。给定一些可选的麦片,奶牛会执行如下的过程:
- 如果她最爱的麦片还在,取走并离开。
- 否则,如果她第二喜爱的麦片还在,取走并离开。
- 否则,她会失望地哞叫一声然后不带走一片麦片地离开。
当你最优地排列这些奶牛时,求饥饿的奶牛的最小数量。同时,求出任意一个可以达到此最小值的 $N$ 头奶牛的排列。
输入格式
无
输出格式
无
说明/提示
【样例解释】
在这个例子中,有 $8$ 头奶牛和 $10$ 种麦片。
注意我们对前三头奶牛独立于后五头奶牛求解,因为她们没有共同喜欢的麦片。
如果前三头奶牛按顺序 $[1,2,3]$ 进行选择,则奶牛 $1$ 会选择麦片 $2$,奶牛 $2$ 会选择麦片 $3$,奶牛 $3$ 会饥饿。
如果前三头奶牛按顺序 $[1,3,2]$ 进行选择,则奶牛 $1$ 会选择麦片 $2$,奶牛 $3$ 会选择麦片 $3$,奶牛 $2$ 会选择麦片 $4$;没有奶牛会饥饿。
当然,还存在其他排列使得前三头奶牛均不饥饿。例如,如果前三头奶牛按顺序 $[3,1,2]$ 选择,则奶牛 $3$ 会选择麦片 $2$,奶牛 $1$ 会选择麦片 $1$,奶牛 $2$ 会选择麦片 $3$;同样,奶牛 $[1,2,3]$ 均不会饥饿。
可以证明在后五头奶牛中,至少一头会饥饿。
【数据范围】
- $14$ 个测试点中的 $4$ 个测试点满足 $N,M\le 100$。
- $14$ 个测试点中的 $10$ 个测试点没有额外限制。
【说明】
本题采用自行编写的 [Special Judge](https://www.luogu.com.cn/paste/hi36jkwh)。如果对此有疑问或想要 hack,请[私信编写者](https://www.luogu.com.cn/chat?uid=137367)或[发帖](https://www.luogu.com.cn/discuss/lists?forumname=P8095)。