小红书笔试 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)) 