pdd 笔试 第三题 动态规划
n,m,t = list(map(int, input().split()))
arr=[[],[]]
for i in range(n):
a,b = list(map(int, input().split()))
arr[0].append([a,b])
for i in range(m):
a,b = list(map(int, input().split()))
arr[1].append([a,b])
ans=float('inf')
dp=[ans]*(t+2)
dp[0]=0
arr[0].sort(key=lambda x:x[1],reverse=True)
for rl,mw in arr[0]:
mw=min(mw,t)
dp[mw]=min(dp[mw],rl)
for i in range(t,0,-1):
dp[i]=min(dp[i+1],dp[i])
ans=min(ans,dp[t])
arr[1].sort(key=lambda x:x[0])
for rl,mw in arr[1]:
x=t-mw
x=max(0,x)
ans=min(ans,dp[x]+rl)
if ans==float('inf'):
print(-1)
else:
print(ans)
现在看，两个sort没有什么必要，反正中餐晚餐都需要枚举一遍
顺便贴上第一题的
k,n = list(map(int, input().split()))
arr = list(map(int, input().split()))
ans=0
cnt=0
for i,x in enumerate(arr):
if ans==k:
print('paradox')
exit()
else:
if ans+x<=k:
ans += x
else:
ans=k-(ans+x-k)
cnt+=1
print(abs(k-ans),cnt)
