拼多多笔试

Python复盘http://www.twistedwg.com/2019/07/29/algorithm_1.html

经过和lz等本讨论帖等人的讨论，完善了下思路，对于长度相同的情况没必要去重，只需增加一个长度的判断，放python代码如下，欢迎纠错 import sys line = sys.stdin.readline().strip() while line: line = sys.stdin.readline().strip() L = list(map(int, line.split())) line = sys.stdin.readline().strip() W = list(map(int, line.split())) n = len(L) arr = [(l, w) for (l, w) in zip(L, W)] arr = sorted(arr, key=lambda x: x[0]) ls, ws = [0] * n, [0] * n ls[0], ws[0] = 1, arr[0][1] for i in range(1, n): ls[i], ws[i] = ls[i - 1], ws[i - 1] for j in range(i): if arr[i][1] * 7 >= ws[j] and arr[j][0] < arr[i][0]: if ls[j] + 1 > ls[i]: ls[i] = ls[j] + 1 ws[i] = ws[j] + arr[i][1] elif ls[j] + 1 == ls[i]: ws[i] = min(ws[j] + arr[i][1], ls[i]) print(ls[n - 1]) line = sys.stdin.readline().strip()

不是dl，只ac10%，说一个思路，抛砖引玉，首先根据长度对积木排序，积木的长度和重量是绑定的，排序的话，注意不要改变其对应关系，python实现很简单，长度重量绑定成元组，然后对长度排序。用动态规划，lengths[i]表示[0, i]区间内最高的金字塔，weights[i]表示其对应重量，对于每一个i遍历j，j<i, 如果W[i] * 7 >= weights[i], lengths[i] = max(lengths[j] + 1, lengths[i]), 时间复杂度O(n^2)。当时没有做判断的一点是如果lengths[j] + 1 == lengths[i]，应该要比较weights[j] + W[i]与当前weights[i]的大小，若小则更新。还有一点关于输入的疑问，会不会存在长度相同但重量不同的积木，如果有，想先做去重，只保留重量最轻的。