我陷入了一个问题。我知道dp可以在这里应用，但不能得到它。
考虑从0开始到10^9结束的正数行的一部分。从0开始，可以执行N个任务。
ith任务处于l[i]并且需要执行t[i]时间。要执行ith任务，您必须到达点l[i]，并在该位置花费时间t[i]。
在路径上行驶一个单元需要1秒，即从1到3需要(3-1(=2秒。
你有T秒的时间，在这段时间里，你必须尽可能多地执行任务，然后回到起始位置。我需要找到在时间T内可以执行的最大值。
示例
考虑M=3，T=10，l[]=[1，2]，T[]=[3，2]。
如果我们执行第一个任务，则消耗的总时间为1(旅行(+3(完成任务(=4。剩余时间为10-4=6。
现在，如果我们连续执行第二个任务，所花费的总时间是1(从1开始(+2(完成任务(=3。剩余时间为6-3=3。
现在，如果我们从2返回到0。所花费的总时间为2。剩余时间为3-2=1。因此，我们可以在给定的时间内安全地完成这两项任务。所以答案是2。
约束很高：
1 <= N <= 10 ^ 5
0 <= T <= 10 ^ 8
0 <= l[i], t[i] <= 10 ^ 9
有一个最优解决方案，我们从0到某个坐标x，然后返回，贪婪地选择从最短到最长的区间[0，x]中的任务。
可能有一个动态编程解决方案，但这不是我首先想要的。相反，我会使用一种扫描线算法，将x从0增加到T/2，从而保持最佳解。当x超过l[i]时，我们将任务i添加到议程中。每当当前议程占用太多时间时，我们就会放弃最长的任务。
该算法在Python中看起来像这样(未经测试(。
import heapq
def max_tasks(T, l, t):
x = 0
heap = []
opt = 0
# Sweep the tasks left to right
for l_i, t_i in sorted(zip(l, t)):
# Increase x to l_i
T -= 2 * (l_i - x)
x = l_i
# Add task i to the agenda
T -= t_i
# This is a min-heap, but we want the longest tasks first
heapq.heappush(heap, -t_i)
# Address a time deficit by dropping tasks
while T < 0:
if not heap:
# Travelled so far we can't do any tasks
return opt
# Subtract because the heap elements are minus the task lengths
T -= heapq.heappop(heap)
# Update the optimal solution so far
opt = max(opt, len(heap))
return opt