关注
第一题我大概敲了5 6分钟的样子就实现了, 第二题,看过组合数学这本书,第一小问是个公式题,答案是C(n + m - 1,m),证明我忘了,稍稍有点巧妙,但是公式还记得,对于这个问题的更通用解决办法好像是利用容斥原理,第二小问就是组合数学的乘法计数原理 第三题的话,我先答了一个暴力的做法,和一个先判断是否在X范围内,再判断的简单小优化,然后我考虑的是用数据结构优化,分别是建一棵KD树,每次查询离圆心最近点,期望的复杂度是logn级别的,然后如果小于半径,说明这个点是OK的,然后从KD树删除这个点,期望的复杂度是mlogn,m为在范围内怪物的个数,然后我提到在游戏里,一个场景一般不大可能的50 60%的怪物都被一个技能命中,所以可以肯定这个m很小。 另外办法是四叉树,然后可以缩小枚举区间。 回答完以后,线下自己后来又想了一下,还可以通过离散所有点的坐标,这样所有点的坐标都是正负10W以内,可以通过在圆心向外作BFS之类的,优先访问最近的点,尽可能往外扩展,似乎也是个还凑合的办法。
查看原帖
点赞 8
相关推荐
点赞 评论 收藏
转发
牛客热帖
正在热议
# 牛友的五一计划 #
6702次浏览 185人参与
# 如何一边实习一边秋招 #
199477次浏览 3975人参与
# 牛客帮帮团来啦!有问必答 #
386882次浏览 7677人参与
# 如何看待offer收割机的行为 #
191534次浏览 2963人参与
# 春招别灰心,我们一人来一句鼓励 #
20350次浏览 301人参与
# 无实习如何秋招上岸 #
170699次浏览 2698人参与
# 硬件人的春招flag #
14445次浏览 199人参与
# 晒一晒我的offer #
2807241次浏览 49770人参与
# 非技术岗薪资爆料 #
7150次浏览 135人参与
# 你更愿意参加线上面试还是线下面试? #
6633次浏览 92人参与
# 华为求职进展汇总 #
439685次浏览 4420人参与
# 第一次面试 #
15902次浏览 241人参与
# 在国企工作的人,躺平了吗? #
72024次浏览 874人参与
# 简历中的项目经历要怎么写 #
379033次浏览 6373人参与
# 通信硬件薪资爆料 #
145929次浏览 1099人参与
# 来聊聊机械薪资天花板是哪家 #
21281次浏览 169人参与
# 机械人怎么评价今年的华为 #
54357次浏览 449人参与
# 应届生应该先就业还是先择业 #
12242次浏览 115人参与
# 如果校招重来我最想改变的是 #
71846次浏览 1384人参与
# 租房前辈的忠告 #
21001次浏览 1666人参与