美团8.20算法岗笔试

1.定位


'''
题目描述:
小团在地图上放了三个定位装置,想依赖他们来进行定位!
小团的地图是一个n×n的一个棋盘,他在(x1,y1),(x2,y2),(x3,y3) xi,yi ∈ Z ∩ [1,n] 这三个位置分别放置了一个定位装置(两两不重叠)。
然后小团在一个特定的位置(a,b)a,b ∈ Z ∩ [1,n]放置了一个信标。每个信标会告诉小团它自身到那个信标的曼哈顿距离,即对i=1,2,3 小团知道(|xi-a|+|yi-b|),
现在小团想让你帮他找出信标的位置!注意,题目保证最少有一个正确的信标位置。
因为小团不能定位装置确定出来的信标位置是否唯一,如果有多个,输出字典序最小的那个。(a,b)的字典序比(c,d)小,当且仅当 a<c或者a==c∧b<d

第一行一个正整数n,表示棋盘大小。

第二行两个整数,分别表示x1与y1,即第一个定位器的位置。

第三行两个整数,分别表示x2与y2,即第二个定位器的位置。

第四行两个整数,分别表示x3与y3,即第三个定位器的位置。

第五行三个整数,分别表示第一、二、三个定位器到信标的曼哈顿距离。第i个定位器到信标的曼哈顿距离即(|xi-a|+|yi-b|)

数字间两两有空格隔开,对于所有数据, n≤50000,  1≤xi,yi≤n

'''
n = int(input())
x1, y1 = map(int, input().strip().split())
x2, y2 = map(int, input().strip().split())
x3, y3 = map(int, input().strip().split())
dis1, dis2, dis3 = map(int, input().strip().split())
hash1, hash2, hash3 = dict(), dict(), dict()
for i in range(1, n+1):
    for j in range(1, n+1):
        if abs(i-x1)+abs(j-y1) == dis1:
            hash1[(i,j)] = 1
        if abs(i-x2)+abs(j-y2) == dis2:
            hash2[(i,j)] = 1
        if abs(i-x3)+abs(j-y3) == dis3:
            hash3[(i,j)] = 1
# res = dict()
resdict = dict(hash1.items() & hash2.items() & hash3.items())
common = []
for key, val in resdict.items():
    # for i in range(0, val):
    common.append(key)
x, y = common[0]
print(x,y)

2.复习

'''
小美即将进行期末考试!小美现在盘算了一下,一共有n道试题,对于第 i 道试题,小美有着pi的概率做对,获得ai的分值,
另外(1-pi)的概率做错,获得0分。小美的总分即是每道题获得的分数之和。小美不甘于此!她决定突击复习,因为时间有限,
她最多复习m道试题,使得复习后的试题正确率提升到100%。小美想知道,如果她以最佳方式进行复习,能获得的期望总分最大是多少。
输入描述
第一行两个正整数n和m,表示总试题数和最多复习试题数。

接下来一行n个整数,分别为p1 p2...pn,表示小美有pi%的概率,即pi=pi/100的概率做对第i个题。(注意,这里为了简单起见,将概率pi扩张100倍成为整数pi方便输入)

接下来一行n个整数,分别表示a1 a2...an,分别表示第 i 个题做对的分值。

数字间两两有空格隔开,对于所有数据,1≤m≤n≤50000,0≤pi≤100,1≤ai≤1000

输出描述
输出一行一个恰好两位的小数,表示能获得的最大期望总分。(如果答案为10应输出10.00,2.5应输出2.50)
'''
n, m = map(int, input().strip().split())
num1 = list(map(int, input().strip().split()))
num2 = list(map(int, input().strip().split()))
# print(num1)
path = 0
hashmap = dict()
for i in range(n):
    hashmap[num1[i]] = num2[i]
hashmap = sorted(hashmap.items(), key=lambda kv:(100-kv[0])*kv[1], reverse=True)
res = 0
# print(hashmap[0][1])
for i in range(len(hashmap)):
    if i<m:
        res += 100*hashmap[i][1]
    else:
        res += hashmap[i][0]*hashmap[i][1]
res /= 100
print('%.2f'%res)

3.烤串

'''
题目描述:
 小团想要自己来烤串!不过在烤串之前,需要串好烤串。小团有n个荤菜和n个素菜,他想按顺序分别一个荤菜一个素菜串起来,想请你帮他串好!
给出两个长度分别为n的仅包含小写英文字母的串A和B,分别代表荤菜和素菜的种类(用字母来表示菜的种类)。请你以从左到右的顺序依次串好他们!例如对于荤菜串A1A2...An
和素菜串B1B2...Bn,串好应该是A1B1A2B2...AnBn

输入描述
第一行一个正整数n,表示烤串长度

第二行为一个长度为n的字符串A,表示荤菜按次序都是哪些菜。

第三行为一个长度为n的字符串B,表示素菜按次序都是哪些菜。

对于80%的数据,n≤1000

对于20%的数据,n≤50000

对于所有数据,A和B为仅包含小写英文字母的字符串。

输出描述
输出一行,包含2n个字符串表示串好的烤串。
'''
n = int(input())
str1 = list(map(str, input().strip()))
str2 = list(map(str, input().strip()))
i1, i2 = 0, 0
res = ''
while i1<n and i2<n:
    res += str1[i1]
    i1 += 1
    res += str2[i2]
    i2 += 1
print(res)

4.拟合

'''
小团生日收到妈妈送的两个一模一样的数列作为礼物!他很开心的把玩,不过不小心没拿稳将数列摔坏了!现在他手上的两个数列分别为A和B,
长度分别为n和m。小团很想再次让这两个数列变得一样。他现在能做两种操作,操作一是将一个选定数列中的某一个数a改成数b,
这会花费|b-a|的时间,操作二是选择一个数列中某个数a,将它从数列中丢掉,花费|a|的时间。小团想知道,他最少能以多少时间将这两个数列变得再次相同!

输入描述
第一行两个空格隔开的正整数n和m,分别表示数列A和B的长度。

接下来一行n个整数,分别为A1 A2...An

接下来一行m个整数,分别为B1 B2...Bm

对于所有数据,1≤n,m≤2000, |Ai|,|Bi|≤10000

输出描述
输出一行一个整数,表示最少花费时间,来使得两个数列相同。
'''
n, m = map(int, input().strip().split())
arr1 = list(map(float, input().strip().split()))
arr2 = list(map(float, input().strip().split()))
times = 0
i1, i2 = 0, 0
while i1<len(arr1) and i2<len(arr2):
    if abs(arr2[i2]-arr1[i1]) < abs(arr2[i2])+abs(arr2[i1]):
        times += abs(arr2[i2]-arr1[i1])
        i1 += 1
        i2 += 1
    else:
        times += abs(arr2[i2])+abs(arr2[i1])
        arr1.pop(i1)
        arr2.pop(i2)

print('%.0f'%times)

#美团笔试##算法工程师##秋招##做完美团2023秋招笔试,你还好吗#
全部评论
那个复习是真的狗,只有45
1 回复
分享
发布于 2022-08-20 12:14 浙江
第四题贪心应该有短视的问题  但是我写dp超时了 有没有大佬有用Python过第四题的解法呀
点赞 回复
分享
发布于 2022-08-20 12:35 北京
饿了么
校招火热招聘中
官网直投
吓死我,刚写完转了一圈大家说有五个编程题,我还使劲回想我到底哪个题没做
点赞 回复
分享
发布于 2022-08-20 12:52 广东
第四题楼主A了多少啊
1 回复
分享
发布于 2022-08-20 12:29 上海
求问定位那一题您的解法能ac吗,类似思路只有18
点赞 回复
分享
发布于 2022-08-20 12:50 北京
大佬们可以试试安克创新哟~ 安克创新科技股份有限公司校招内推码: M3DC11M 投递链接: https://anker-in.jobs.feishu.cn/s/ja2wCCq
1 回复
分享
发布于 2022-08-22 16:09 湖南
复习那个题,自测好几次都是对的,就是最后过不了,根本不知道哪的问题😓
点赞 回复
分享
发布于 2022-08-20 12:30 河南
第四题这样做,ac不了吧,其他题倒是蛮简单的
点赞 回复
分享
发布于 2022-08-20 12:32 湖南
第五题发一下可以吗 还没来及做就没时间了
点赞 回复
分享
发布于 2022-08-20 16:11 广东
这是投的什么岗位的题?
点赞 回复
分享
发布于 2022-08-20 18:13 山东
所提代码都能全AC吗,感觉有些不可以啊
点赞 回复
分享
发布于 2022-08-20 23:36 广东
https://www.nowcoder.com/discuss/1022707 全ac的可以看我的~
点赞 回复
分享
发布于 2022-08-21 15:29 北京
欢迎大家投递地平线,算法开发芯片产品等多岗位,北京上海南京杭州等多地点:https://horizon.hotjob.cn/,内推码:crecvy
点赞 回复
分享
发布于 2022-08-21 22:51 江苏
理想汽车2023提前批校招目前已开启,有打算找工作的师弟师妹们,可以通过以下链接内推投递,全程进度跟随,无笔试。 https://www.nowcoder.com/discuss/1008400
点赞 回复
分享
发布于 2022-08-21 23:30 北京
一共5题,wa了好久,总共1个小时多一点ak了,还剩45+min 整体上看都是简单题+中等题
点赞 回复
分享
发布于 2022-08-22 09:40 香港
祝同学秋招顺利哦~期待咱们美团见~ 另外偷偷透露一下~ 算法策略专场直播是在8月24日晚上(19:00-20:00)开始哦~感兴趣的小伙伴赶快拉上小伙伴一起来看哦~ —————————————————————— 直播预告的分割线~ 技术校招生们,如果还有其他关于求职的问题,那么你一定不能错过! 8月24日14:00-22:00,《美团请回答》特别节目“8小时不间断技术校招直播”,邀请美团8大技术方向通道委员+学长倾囊解惑!一次讲清楚所有技术方向,现场拆解笔面试,还有海量礼品相赠,欢迎来观看! 🟡方式一>>微信搜索【美团招聘】视频号,首页进直播 🟡方式二>>来B站直播间:http://live.bilibili.com/22355025 8小时岗位直播流程见:https://www.nowcoder.com/discuss/1019574,评论帖子HR在线回答哦
点赞 回复
分享
发布于 2022-08-22 14:47 北京

相关推荐

26 71 评论
分享
牛客网
牛客企业服务