05-08 17:53 西安邮电大学 电气类
关注
#牛客在线求职答疑中心#： ： 当上了宣传委员，开始组织迎新晚会，已知班里有 个同学，每个同学有且仅有一个擅长的声部，把同学们分成恰好 组，为了不搞砸节目，每一组里的同
学都必须擅长同一个声部，当然，不同组同学擅长同一个声部的情况是可以出现的，毕竟一个声部也可以分成好几个part进行表演，但是他不希望出现任何一组
的人过多，否则可能会导致场地分配不协调，也就是说，她希望人数最多的小组的人尽可能少，除此之外，对组内人员分配没有其他要求，她希望你告诉她，这
个值是多少，如果无法顺利安排，请输出-1
输入描述：第一行两个数个数n,m(1≤m≤n≤100000)表示人数
接下来一行n个数,a[i](1≤a[i]≤n)表示第i个学生的擅长声部
输出描述：输出一个数，表示人数最多的小组的人数
学都必须擅长同一个声部，当然，不同组同学擅长同一个声部的情况是可以出现的，毕竟一个声部也可以分成好几个part进行表演，但是他不希望出现任何一组
的人过多，否则可能会导致场地分配不协调，也就是说，她希望人数最多的小组的人尽可能少，除此之外，对组内人员分配没有其他要求，她希望你告诉她，这
个值是多少，如果无法顺利安排，请输出-1
输入描述：第一行两个数个数n,m(1≤m≤n≤100000)表示人数
接下来一行n个数,a[i](1≤a[i]≤n)表示第i个学生的擅长声部
输出描述：输出一个数，表示人数最多的小组的人数
全部评论
AI牛可乐
带#牛客在线求职答疑中心#提问都会召唤我
这个问题可以通过贪心算法来解决。首先，我们需要统计每个声部的人数。然后，我们按照人数从多到少排序声部。接着，我们选择人数最多的声部，将其分配给第一组。然后，我们选择人数第二多的声部，将其分配给第二组，并更新人数最多的声部的人数。我们重复这个过程，直到所有的同学都被分配到组中。最后，我们输出人数最多的小组的人数。这个问题的时间复杂度是O(n log n)，其中n是学生的人数。
送花
回复
分享
相关推荐
投递埃科光电等公司9个岗位 > 点赞 评论 收藏
转发
点赞 评论 收藏
转发
04-21 11:24
门头沟学院 机械类 点赞 评论 收藏
转发