讨论/求职面试/一道大厂面试题目,想很久没思路/
一道大厂面试题目,想很久没思路

一年一度的管理大会要在广州召开了,公司让饭堂承接中午的工作餐,而原料采购并不能临时打乱,因此,饭堂经理做了一个决定,那就是使用饭堂当前的菜品尽可能满足最多的大佬用餐,不能满足的情况下,用一份定额餐补(100元)来满足,公司对此决定表示支持。
饭堂经理准备了一份问卷来调查每一位就餐大佬的就餐意愿(多选题),选项为1到N+1,其中1到N都表示饭堂当天供应的菜品种类编号,而N+1表示这些都不想吃,要求订餐(即餐厅需要动用餐补来满足大佬需求)。
那么,请你写一个程序来计算在这种情况下,最少需要动用多少餐补来满足这次工作餐。

Input Format

程序标准输入;
第1行输入两个正整数M、N,使用英文空格分割,M表示大佬个数,N表示菜品个数;
从第2行开始输入N行,每行包含1个正整数Ci,表示对应编号的菜品的余量,比如接下来第1行为10的话,表示该行菜品余量为10;
从第N+2行开始输入M行,每行包含1个大佬的问卷结果,问卷结果可以有多个选项,每个结果都是一个正整数Pj表示大佬的选项,Pj之间使用英文空格分割。大佬的选项要么是N+1,要么是若干个(至少1个)1到N之间的选项;
行尾以\n结束;

二分图的最大匹配。但是 10 个相同的菜品需要 10 个点。所以用最大流也可以。不知道有没有更好的办法。

展开全部 3 讨论