小红书笔试 AC代码
第二题 dp
def solution(nums): n = len(nums) dp1 = nums[:] dp2 = [1] * n for i in range(n): for j in range(i-1): if dp1[i] < dp1[j] + nums[i]: dp1[i] = dp1[j] + nums[i] dp2[i] = dp2[j] + 1 idx = dp1.index(max(dp1)) return dp1[idx], dp2[idx] import sys n = int(sys.stdin.readline().strip()) line = sys.stdin.readline().strip() nums = list(map(int, line.split())) res = solution(nums) print(' '.join(map(str, res)))第三题 贪心,二分
def list2gen(a): for n in a: yield n def ismatch(X): # 在达到目标时输出X fali_need = 0 for Hi in list2gen(H): fali_need += Hi // X # fali_need = sum([Hi // X for Hi in H]) # 法力不够,用物理攻击弥补 if fali_need >= M: wuli_need = X * (fali_need - M) for Hi in list2gen(H): wuli_need += Hi % X # wuli_need += sum([Hi % X for Hi in H]) if M + fali_need <= T: return True else: return False # 法力超出,多出来的这样用 # X=3,Hi=2,这样使用一次 else: yushu = sorted([Hi % X for Hi in H]) wuli_need = sum(sorted(yushu)[::-1][M - fali_need :]) if M + wuli_need <= T: return True else: return False def solution(N, T, M, H): H = sorted(H)[::-1] # 特殊情况 if M + sum(H[M:]) > T: return -1 l = (sum(H) - (T - M)) // M r = H[0] # print(l, r) while l < r: mid = l + ((r - l) >> 1) # print(f'mid: {mid}') if ismatch(mid): r = mid else: l = mid + 1 return l import sys line = sys.stdin.readline().strip() N, T, M = list(map(int, line.split())) line = sys.stdin.readline().strip() H = list(map(int, line.split())) print(solution(N, T, M, H))