AcWing 1090. 绿色通道 二分搜索+单调队列优化DP
原题链接
中等
作者:
皓首不倦
,
2020-07-29 18:54:45
,
所有人可见
,
阅读 690
'''
二分搜索可能的空题段的长度,用单调队列优化的DP验证此
空题段长度下,能够找到合法的选择方案
'''
from collections import deque
n, t = map(int, input().split())
arr = list( map(int, input().split()) )
# 验证空题段长度为m,是否有可行方案
def valid(emp_len):
# dp(i)表示前i个作业中做选择, 最后一个作业做了的情况下,总开销最小值
# dp(i) = arr[i] + min(dp(i-1), dp(i-2), dp(i-m))
# 用单调队列进行计算优化
dp = [0] * n
que = deque()
for idx, val in enumerate(arr):
if idx <= emp_len-1:
dp[idx] = arr[idx]
else:
dp[idx] = arr[idx] + que[0][1]
while len(que) > 0 and idx - que[0][0] >= emp_len:
que.popleft()
while len(que) > 0 and dp[idx] <= que[-1][1]:
que.pop()
que.append( (idx, dp[idx]) )
return min( dp[-emp_len:] ) <= t
ans = -1
l, r = 1, n
while l <= r:
mid = l + (r-l) // 2
if valid(mid):
ans = mid
r = mid - 1
else:
l = mid + 1
if ans == -1:
print(n)
else:
print(ans-1)