第一题我大概敲了5 6分钟的样子就实现了, 第二题,看过组合数学这本书,第一小问是个公式题,答案是C(n + m - 1,m),证明我忘了,稍稍有点巧妙,但是公式还记得,对于这个问题的更通用解决办法好像是利用容斥原理,第二小问就是组合数学的乘法计数原理 第三题的话,我先答了一个暴力的做法,和一个先判断是否在X范围内,再判断的简单小优化,然后我考虑的是用数据结构优化,分别是建一棵KD树,每次查询离圆心最近点,期望的复杂度是logn级别的,然后如果小于半径,说明这个点是OK的,然后从KD树删除这个点,期望的复杂度是mlogn,m为在范围内怪物的个数,然后我提到在游戏里,一个场景一般不大可能的50 60%的怪物都被一个技能命中,所以可以肯定这个m很小。 另外办法是四叉树,然后可以缩小枚举区间。 回答完以后,线下自己后来又想了一下,还可以通过离散所有点的坐标,这样所有点的坐标都是正负10W以内,可以通过在圆心向外作BFS之类的,优先访问最近的点,尽可能往外扩展,似乎也是个还凑合的办法。
点赞 8

相关推荐

从去年秋招开始,到最近春招,一共面了🐧的三个岗位,时间线如下:-----PCG-大数据平台-后台开发-----一面:2024/9/3二面:2024/9/4(SQL没撕出来,挂了)(这个还算正常,后面的就开始抽象起来了)-----TEG-研发管理部-后台开发-----一面:2024/9/11二面:2024/9/18三面:2024/9/27HR面:2024/10/9(泡了几个月,排序挂)(此时HR面过了之后先是面评没提交导致自动挂然后邮件联系又拉起来了,之后就是录用评估中状态一直从24年10月卡到了25年3月,简直硬控我4个多月,令人忍俊不禁。。。😅)-----IEG-魔方工作室-后台开发-----一面:2025/3/27二面:2025/4/2HR面:2025/4/8(一周后排序挂)(因为秋招已经签了三方,所以春招就简单投了投,随后就被该岗位给捞了,据面试官介绍是做暗区突围海外版后端的(游戏服务器,还是海外非核心,只能说buff叠满了。。。😂),面完两轮技术面就进HR面了,当时就感觉有点奇怪,随后面完HR面泡了一周多的池子排序挂掉了,估计是因为已经签三方了😢)自从之前在🐧WXG实习了几个月转正失败跑路以来,就还是想再当一回🐧孝子(有鹅选鹅的含金量),但是造化弄人,面了三个岗,两个排序挂(要是技术面挂其实还能接受,排序挂是真的难绷。。。😭),最终还是只能遗憾离场了啊啊啊啊,我直接化身🐧黑子了#校招# #腾讯# #秋招你被哪家公司挂了?# #春招进度记录#
点赞 评论 收藏
分享
牛客网
牛客企业服务