美团算法岗第三场笔试

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出来，下次美团笔试再见了😅😅😅
#美团求职进展汇总# #美团#