2018年 6月MTV狗家昂赛

eshang 发表于 2018-7-23 11:11
其实party这题应该用类似topo sort来做，感觉楼主这个算法不对啊，可能挂了就是因为这道题吧

topo 是 O(V + E),也就是O(n)比整理快吧？

party正确解法应该是这样，每轮统计有多少个人是小于等于1的，然后把这些人删除，其他的人的人数减去这一轮移除的人数，重复直到没有人了或者这轮找不到人来移除了，O(n)时间。

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

josephdesire 发表于 2018-7-24 04:30
我怎么觉得用heap就够了？ 初始化人数是1 然后查看heap中最小人数要求的 如果满足条件 就增加一个人数 直 ...

本质上来说还是topo的思路，O（V+E），只不过数据结构更优化点吧？

太空牛仔 发表于 2018-7-25 05:57
本质上来说还是topo的思路，O（V+E），只不过数据结构更优化点吧？

所以bfs就行了吗

感谢楼主详细分享

太空牛仔 发表于 2018-7-25 05:57
本质上来说还是topo的思路，O（V+E），只不过数据结构更优化点吧？

这不是图的题，只是gready而已。。。

party这题应该类似h-index, 用上界n人的bucket-sort 可以O(n), 如果用heap的话heapify O(n) 但是之后pop都是log(n), 应该还是O(nlogn) ;

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies