拼多多算法笔试交流（AC 2.6）
拼多多第三第四题好折磨人啊，都是10^12的大小，感觉需要推导出来公式才能AC，难，我只能用简单办法试试了。求一个第三第四题思路，我把我的先贴出来（第四题实在写得乱，只能A最基础的20%，就不拿出来了）
第一题 AC 100%
import sys """ 给定N个数字，与操作次数M M次取两个数，求最后这M个乘积的最小值 不可重复使用 测试用例： 4 2 1 2 3 4 10 """ if __name__ == "__main__": # 读取第一行的n n, m = [int(e) for e in sys.stdin.readline().strip().split()] A = list(map(int, sys.stdin.readline().strip().split())) A.sort() A = A[:m*2] res = 0 for i in range(m): res += A[i]*A[2*m-i-1] print(res)第二题 AC 100%
import sys """ 种树，给一个区间，与M个人种树的区间 每次有人种树，得到此时的树的数量 测试用例： 4 3 1 2 2 3 3 4 2 3 4 """ if __name__ == "__main__": # 读取第一行的n n, m = [int(e) for e in sys.stdin.readline().strip().split()] lst = [] for i in range(m): lst.append(list(map(int, sys.stdin.readline().strip().split()))) tree = [0] * n count = 0 for e in lst: i = e[0]-1 while i < e[1]: if tree[i] != 0: i = tree[i] else: tree[i] = e[1] i+=1 count += 1 print(count)
第三题 AC 40%
import sys
"""
给定m,n . 最多由m个a,n个b组成一个字符串，求所有字符串中排序为K的那个字符串
超时，通过40%
"""
if __name__ == "__main__":
# 读取第一行的n
n, m, k = [int(e) for e in sys.stdin.readline().strip().split()]
# print(n,m,k)
global count
global res
count = 0
if k <= n:
print("a"*k)
exit(0)
# elif k<n+m:
# print("a"*(k-n)+"b"*(k-n))
def rev(a_num, b_num, s, K):
global count
global res
if count == K:
res = s
print(res)
exit(0)
elif count < K:
count += 1
if a_num>0:
rev(a_num-1, b_num, s+"a", K)
if b_num>0:
rev(a_num, b_num-1, s+"b", K)
rev(n, m, "", k) 
