社区讨论
站外题求助必关!!!
灌水区参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @m4skqjl2
- 此快照首次捕获于
- 2024/12/17 22:43 去年
- 此快照最后确认于
- 2024/12/18 16:28 去年
小 F 和大 F 开了一所幼儿园,春天到了,幼儿园要举办一场运动会! 幼儿园里有 N 个小朋友,运动会里有 M 个项目可供选择,每个小朋友都对 M 个项目有 一定的喜好程度。对于第 i 个小朋友,他第 j 喜欢的项目是 aij。并且保证对于每个小朋友, 他都不会有两个一样喜欢的项目。 幼儿园的园长小 F 和副园长大 F 对运动会的事情头疼不已,她们希望玩的人数最多的项 目玩的人数最少,否则她们在最受欢迎的项目举行时会忙不过来。她们希望从 M 个项目中 选出若干个项目在运动会中举行(可以全选,但不能一个也不选),每个小朋友会且仅会玩 一个项目,并且他玩的项目一定是举行的项目中他最喜欢的。 很不幸,今天幼儿园停电了,电脑不能用,小 F 和大 F 决定将这个问题交给聪明的你, 请你求出玩的人数最多的项目玩的人数的最小值。
输入格式
第 1 行两个整数 N 和 M,表示小朋友的个数和备选运动项目的个数。
第 2 至 N+1 行,每行 M 个整数。第 i+1 行的第 j 个整数表示 aij,表示第 i 个小朋友第 j 喜欢的项目。保证 ai1..aiM 是 1..M 的一个排列。
输出格式
一个整数,表示玩的人数最多的项目玩的人数的最小值。
输入/输出例子1
输入:
4 5
5 1 3 4 2
2 5 3 1 4
2 3 1 4 5
2 5 4 3 1
输出:
2
输入/输出例子2
输入:
3 3
2 1 3
2 1 3
2 1 3
输出:
3
样例解释
【样例 1 解释】
一种最优方案是选择举行 1,3,4 三个项目,这样的话,4 个小朋友玩的项目分别是 1,3,3,4,玩的人数最多的项目是 3,有 2 个人玩,所以答案是 2。
【样例 2 解释】
由于无论怎么选择举行的项目,3 个小朋友玩的项目都是同一个,所以答案一定是 3。
【数据范围】
对于 30%的数据,M<=16。
对于另外 30%的数据,N<=3。
对于100%的数据,1 <= N,M <= 300。
求代码!!!
回复
共 0 条回复,欢迎继续交流。
正在加载回复...