要执行的最大任务数 [英] Maximum number of tasks to be performed

问题描述

我遇到了一个问题.我知道 dp 可以在这里应用，但没有得到它.

考虑从 0 开始到 10^9 结束的正数行的一部分.你从 0 开始，可以执行 N 个任务.

ith<​​/code> 任务在 l[i] 并且需要 t[i] 时间来执行.要执行 ith<​​/code> 任务，您必须到达点 l[i] 并在该位置花费时间 t[i].

在路径上移动一个单位需要一秒，即从 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 ^ 50 <= T <= 10 ^ 80 <= l[i], t[i] <= 10 ^ 9

解决方案

有一个最优解，我们从 0 到某个坐标 x 并返回，贪婪地选择区间 [0, x] 中从最短到最长的任务.

可能有一个动态编程解决方案，但这不是我首先要达到的.相反，我会使用扫描线算法将 x 从 0 增加到 T/2，从而保持最佳解决方案.当 x 通过 l[i] 时，我们将任务 i 添加到议程中.每当当前议程占用太多时间时，我们就会放弃最长的任务.

该算法在 Python 中看起来像这样(未经测试).

import heapqdef max_tasks(T, l, t):x = 0堆 = []选择 = 0# 从左到右扫描任务对于 l_i, t_i in sorted(zip(l, t)):# 增加 x 到 l_iT -= 2 * (l_i - x)x = l_i# 将任务 i 添加到议程中T -= t_i# 这是一个最小堆，但我们首先想要最长的任务heapq.heappush(heap, -t_i)# 通过删除任务解决时间不足当 T <0:如果不是堆:# 走了这么远我们不能做任何任务返回选择# 减去因为堆元素减去任务长度T -= heapq.heappop(heap)# 更新目前的最优解opt = max(opt, len(heap))返回选择

I'm stucking in a problem. I know dp can be applied here, but not getting it.

Consider a part of the positive number line starting at 0 and ending at 10^9. You start at 0 and there are N tasks can be performed.

The ith task is at l[i] and requires t[i] time to be performed. To perform ith task, you've to reach the point l[i] and spend time t[i] at that location.

It takes one second to travel one unit on the path i.e. going from 1 to 3 will take (3 - 1) = 2 seconds.

You are given T seconds of time, in this time you have to perform as many as tasks you can AND return to the start position. I need to find maximum can be performed in time T.

Example

Consider M = 3, T = 10, and l[] = [1, 2], and t[] = [3, 2].

If we perform the 1st task total time consumed is 1 (to travel) + 3 (to do the task) = 4. The remaining time is 10 - 4 = 6.

Now if we perform the 2nd task consecutively, the total time taken is 1 (to travel from 1) + 2 (to do the task) = 3. The time remaining is 6 - 3 = 3.

Now if we return from 2 to 0. The total time taken is 2. The remaining time is 3 - 2 = 1. Therefore we can safely complete both tasks in a given time. So the answer is 2.

Constrains are high:

1 <= N <= 10 ^ 5
0 <= T <= 10 ^ 8
0 <= l[i], t[i] <= 10 ^ 9

解决方案

There is an optimal solution where we travel from 0 to some coordinate x and back, greedily choosing tasks in the interval [0, x] from shortest to longest.

There might be a dynamic programming solution, but it's not what I would reach for first. Rather, I'd use a sweep-line algorithm that increases x from 0 to T/2, maintaining an optimal solution. When x passes l[i], we add task i to the agenda. Whenever the current agenda uses too much time, we drop the longest task.

The algorithm looks something like this in Python (untested).

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

这篇关于要执行的最大任务数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！