美团算法岗第三场笔试
5道题
美团,longlong安利者,以后做美团有一个int算我输😅😅
1.判断像素像素分辨率
有点绕的签到题
根据长宽分别是360p 480p 720p 1080p 4k
其实关键就是看最小值,只要最小值在对应的区间,比如[480,720),就输出对应分辨率就可以
2.取瓶子
输入起点坐标ab,终点cd,瓶子数量n
之后输入n个瓶子的坐标
每次移动瓶子需要花费曼哈顿距离的代价,求将所有瓶子移动到终点所需的最小代价
实际上只有一次从起点到瓶子到终点距离d1,其余都是从终点到瓶子到终点d2,
所以实际上就是求这两个距离之差d2-d1的最大值,最后在减去即可
感觉思路没问题,死活只能a30%,不知道为什么😭
修订,思路没问题,找到问题所在了,坐标虽然是10e9,可以被int表示,但是运算时会溢出,所以坐标必须用long long,我只有距离用了long long,所以爆了😅😅
3.乘积最大
输入abck四个整数,k意味着可以进行k次操作,每次操作选择abc中其中一个加一,输出abc最大乘积
我的思路是把最小的依次抹平,min先加到mid,多出来min和mid平分,有余1加到mid上,如果都能加到max,则max和min和mid三者平分,根据余2还是余1分别再加到max和mid上
最后对10e9+7取模
感觉思路没问题,死活只能a30%,不知道为什么😭
修订,应该是每次运算都需要对mod取模,我其实想到了,但我忘了一次😅😅😅。
4.树的最大权值
输入一颗n节点的树,每个节点有对应值ai,求在节点uv之间加一个边,使得其成为一个环,而且这个环的权值要最大,环的权值定义为这个环上节点值未出现过的最小整数,就是之前那个mex。
这tm一眼寄,感觉需要dfs+最近祖先+dp之类的,我直接投降
5.买东西
有n件商品,按照编号一次摆开,之后依次输入n个整数代表每件商品有对应保质,之后输入n个01,代表商品的种类有两种,意味着每件商品不是0就是1。
之后进行n次购买,输入l,r,t,k,代表购买从在[l,r]区间挑选,t代表要购买的商品类型,k代表要购买的商品种类。 购买标准为买这个区间内保质期最长的对应种类商品,若保质期一致,优先购买编号小的,若购买件数未达到标准,在购买商品编号后面补充输出-1。每次购买是在上次购买的结果上进行的。
一眼线段树,完全没学。所以直接超时做法,每次在区间进行排序,最后a了20%。
直接纯寄,两道明明有思路感觉没问题的都没a出来,下次美团笔试再见了😅😅😅
#美团求职进展汇总# #美团#
美团,longlong安利者,以后做美团有一个int算我输😅😅
1.判断像素像素分辨率
有点绕的签到题
根据长宽分别是360p 480p 720p 1080p 4k
其实关键就是看最小值,只要最小值在对应的区间,比如[480,720),就输出对应分辨率就可以
2.取瓶子
输入起点坐标ab,终点cd,瓶子数量n
之后输入n个瓶子的坐标
每次移动瓶子需要花费曼哈顿距离的代价,求将所有瓶子移动到终点所需的最小代价
实际上只有一次从起点到瓶子到终点距离d1,其余都是从终点到瓶子到终点d2,
所以实际上就是求这两个距离之差d2-d1的最大值,最后在减去即可
感觉思路没问题,死活只能a30%,不知道为什么😭
修订,思路没问题,找到问题所在了,坐标虽然是10e9,可以被int表示,但是运算时会溢出,所以坐标必须用long long,我只有距离用了long long,所以爆了😅😅
3.乘积最大
输入abck四个整数,k意味着可以进行k次操作,每次操作选择abc中其中一个加一,输出abc最大乘积
我的思路是把最小的依次抹平,min先加到mid,多出来min和mid平分,有余1加到mid上,如果都能加到max,则max和min和mid三者平分,根据余2还是余1分别再加到max和mid上
最后对10e9+7取模
感觉思路没问题,死活只能a30%,不知道为什么😭
修订,应该是每次运算都需要对mod取模,我其实想到了,但我忘了一次😅😅😅。
4.树的最大权值
输入一颗n节点的树,每个节点有对应值ai,求在节点uv之间加一个边,使得其成为一个环,而且这个环的权值要最大,环的权值定义为这个环上节点值未出现过的最小整数,就是之前那个mex。
这tm一眼寄,感觉需要dfs+最近祖先+dp之类的,我直接投降
5.买东西
有n件商品,按照编号一次摆开,之后依次输入n个整数代表每件商品有对应保质,之后输入n个01,代表商品的种类有两种,意味着每件商品不是0就是1。
之后进行n次购买,输入l,r,t,k,代表购买从在[l,r]区间挑选,t代表要购买的商品类型,k代表要购买的商品种类。 购买标准为买这个区间内保质期最长的对应种类商品,若保质期一致,优先购买编号小的,若购买件数未达到标准,在购买商品编号后面补充输出-1。每次购买是在上次购买的结果上进行的。
一眼线段树,完全没学。所以直接超时做法,每次在区间进行排序,最后a了20%。
直接纯寄,两道明明有思路感觉没问题的都没a出来,下次美团笔试再见了😅😅😅
#美团求职进展汇总# #美团#
全部评论
都笔试那么多场了啊
美团:抽象鼻祖 每次ac的和都不会超过两道
还真是 我也是这两道题死活只能30 不知道是不是long的原因
我感觉是因为,整数不一定能均分😓,比如1.1.1,总不能变成1.3/1.3/1.3,只能变成2.1.1,但是这应该只是错误原因之一
第二题思路差一点,应该是第一次找起点到瓶子再到终点最近的,其他的都是瓶子到终点距离的2倍
第三题我也同样的思路,也是30
为啥我第一题也是考虑h, w中最小的那个去判断,但是总是卡在50%?
相关推荐
点赞 评论 收藏
分享
东大在逃oj人:跟前端问的只能说毫无关系
点赞 评论 收藏
分享