美团笔试0816

不得不说题目真的有点难了
第二题:
贪心,开两个multiset,分别存A和B,每次取出A和B最大的,如果A的最大值大于B最大值,A最大值丢弃并将原最大值执行操作丢回set,计数+1;如果B最大值大于A最大值,B最大值丢弃并将原最大值执行操作丢回set,计数+1;如果相等,则分别丢弃最大值,计数值不变。最后输出计数值
第三题:
线段树可以做,但是很麻烦#牛客AI配图神器#。有点类似于线段树求逆序对或线段树求最长上升子序列,需要维护对于某个i,在此前遍历的j>i有多少个比i大或小。首先复制一份排序后的数组,从后往前遍历,每个位置j,把所有右边比它大的顺序(k>j,且idx(a[k])>idx(a[j]))的idx(a[k])(idx(x)表示数组排序后,x所在位置)都+1(参考线段树区间逐元素加一个值的维护方式,带染色标记)。这里要注意的是,比某个数大的,在右边未必出现过,所以未出现的地方一开始要用负无穷初始化,出现后才置为整数,然后在线段树递归更新查询的时候维护一个判断条件,为正数才累计求和。这样,遍历到i的时候,可以算出i到k之间,有多少个j产生了贡献,然后把所有k的值求和,就可以了。
全部评论
第三题如果做过三维偏序就很简单,用cdq+树状数组就行,考虑对[l,r]时贡献,i位于[l,mid],k位于[mid+1,r],然后分类讨论下j位于左右的求值方法即可。
2 回复 分享
发布于 08-16 21:10 广东
第二题用优先队列写只过了0.45还不是T, 调不出来
点赞 回复 分享
发布于 08-16 20:58 江苏

相关推荐

08-15 18:01
已编辑
美团_后端(实习员工)
bg学院本末9硕,6月18日在小红书上看到白袜哥宣传后私信,加入学习,当时项目有做黑马点评和外卖,算法刷了hot100,看了一些小林coding的八股,只是面试全挂了。但基础还行,只缺项目和补一下八股,所以学到7月初开始投,7月9日第一次面试美团,到8月1日前还面过快手、京东、字节、滴滴,但全都挂在了一面,答的很好也挂了。小红书本来hr都要约面了,又说有人已经接offer了所以流程中止,丢失面试机会。挫败感还是比较大的,都有点怀疑人生了,白袜哥跟我说是现在hc少,让再沉淀沉淀,但还是觉得很抑郁,明明都准备好了就是没过一面,找白袜哥聊,跟我讲了很多,现在印象比较深的就是他说暑期有合工大硕0实习一面放水,二面被拷打的完全答不出还是过,三面直接聊天躺赢进字节的故事,但还是觉得意难平,主要是在身边发生,一下有点接受不了。二战转折点在下午,面美团感觉相当好,问的所有问题都答出来了,但又有点担心跟之前一样面的好也挂,但这次并没有,面完半小时hr就打来了电话,问我什么可以到岗,有没有其他流程,如果给了offer会不会去,转折来的太突然让我反复怀疑真的面过了吗,即使白袜哥说这就是oc我还是持保留态度,只是把加了hr微信后的聊天记录发他确保沟通不踩雷,然后每隔一段时间刷新下状态翘首以盼。8月3日还出现了插曲,官网显示面试不通过,差点又道心破碎了,问白袜哥是什么情况,他的答复是美团校招官网经常出奇奇怪怪的bug,比如他暑期教的一个双9面美团时拿到的是那个人三年前本科投美团暑期的简历,但我还是怕变成一场空,就按他的意思去问hr,得到的回应是并没有挂,8月1日就已经推进了流程,只是要过周末,于是在忐忑不安中度过了周末。周一上午美团offer终于来了,悬着的心也是彻底放下。整个过程不是很长,但确实很提心吊胆,最后的offer也是一波三折,开始以为又会跟之前一样寄掉,知道要拿offer了开始高兴,看到官网面试未通过的崩溃,最后终于收到offer的释怀还是感谢下白袜哥在回答疑问之余还耐心的听我发牢骚,咏袜@黑皮白袜臭脚体育生8.15更新 补聊天记录
学一下吧现在太菜了:刚面完美团,2道dp一道图论,都有原题,八股也是问一些简单的。面完一面就过了,完事之后美团领导就给发了offer,还给了一个头盔一套制服,不过领导说了,这年头电动车要自己买。
点赞 评论 收藏
分享
脑子烧了,这是什么规律啊。1,10,19,37,64,( )
hl7:0*9+1 1*9+1 2*9+1 4*9+1 7*9+1,9的系数是前两个系数相加再加1?
投递美团等公司10个岗位
点赞 评论 收藏
分享
评论
3
2
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务