关注
第一题我大概敲了5 6分钟的样子就实现了, 第二题,看过组合数学这本书,第一小问是个公式题,答案是C(n + m - 1,m),证明我忘了,稍稍有点巧妙,但是公式还记得,对于这个问题的更通用解决办法好像是利用容斥原理,第二小问就是组合数学的乘法计数原理 第三题的话,我先答了一个暴力的做法,和一个先判断是否在X范围内,再判断的简单小优化,然后我考虑的是用数据结构优化,分别是建一棵KD树,每次查询离圆心最近点,期望的复杂度是logn级别的,然后如果小于半径,说明这个点是OK的,然后从KD树删除这个点,期望的复杂度是mlogn,m为在范围内怪物的个数,然后我提到在游戏里,一个场景一般不大可能的50 60%的怪物都被一个技能命中,所以可以肯定这个m很小。 另外办法是四叉树,然后可以缩小枚举区间。 回答完以后,线下自己后来又想了一下,还可以通过离散所有点的坐标,这样所有点的坐标都是正负10W以内,可以通过在圆心向外作BFS之类的,优先访问最近的点,尽可能往外扩展,似乎也是个还凑合的办法。
查看原帖
点赞 8
相关推荐
点赞 评论 收藏
分享
点赞 评论 收藏
分享
点赞 评论 收藏
分享
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 商战,最累的是我们 #
4158次浏览 21人参与
# 租房找室友 #
19906次浏览 117人参与
# 职场新人生存指南 #
311040次浏览 6427人参与
# 你上一次加班是什么时候? #
56397次浏览 383人参与
# 携程求职进展汇总 #
471775次浏览 3466人参与
# 深信服求职进展汇总 #
183427次浏览 1673人参与
# 学历or实习经历,哪个更重要 #
105181次浏览 724人参与
# 机械人选offer,最看重什么? #
87126次浏览 538人参与
# 秋招想进国企该如何准备 #
53418次浏览 353人参与
# 哪些公司面试官让你印象深刻? #
254846次浏览 2676人参与
# 2023届毁约公司名单 #
187347次浏览 935人参与
# 得物求职进展汇总 #
90147次浏览 791人参与
# 和牛牛一起刷题打卡 #
277283次浏览 6451人参与
# 大疆求职进展汇总 #
483258次浏览 3199人参与
# 查收我的offer竞争力报告 #
172596次浏览 1023人参与
# 如果可以,你希望哪个公司来捞你 #
74702次浏览 323人参与
# 产品面经 #
171113次浏览 1895人参与
# 通信硬件公司评价 #
123438次浏览 405人参与
# 实习要如何选择和准备? #
65420次浏览 1060人参与
# 秋招最大的收获是什么? #
26848次浏览 275人参与