美团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秋招笔试，你还好吗#
但是我写dp超时了 有没有大佬有用Python过第四题的解法呀
整体上看都是简单题+中等题
另外偷偷透露一下～
算法策略专场直播是在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在线回答哦
查看19道真题和解析
