algorithm - 查找每个商店的间隔

Question

您在一行中有 n 家商店，每家商店都有关联的金额 $c_i$。在时间 1，您从商店 1 开始。在随后的每个时间，您都可以选择访问商店 i-1、留在商店 i 或访问商店 i+1。在每个时间步，假设你在商店 i，你可以收取 $c_i$ 钱，不管你已经去过那家商店多少次。

给定时间 $t_j$ 的列表，如果您可以收集 $t_j$ 个时间步长的钱，请找出可以收集的最大金额。

我无法想出一种预处理数据的方法。我的想法是，对于每个摊位，我想找到一个时间间隔，在这个时间间隔内，最好直接冲到那个摊位并呆在那里，在每个时间步收钱。我不确定在 O(n) 时间或 O(nlogn) 时间内有效执行此操作的正确方法。

编辑:我目前正在为每个摊位做的是，我有一个时间函数表达式，表示如果我直接去摊位并呆在那里，我可以收集到的最大金额。然后每次，我都取所有这些函数的最大值。这需要线性时间来处理每次查询。我想要这样做的对数过程。

Answer 1

您的收入函数通过直接去商店返回金额 i并在那里停留给定的总时间t是

r_i(t) = sum(j from 1 to i - 1: c_j) + c_i * (t - i + 1)

可以为每个 i 递增计算总和你会得到一个简洁的线性函数:

r_i(t) = a_i + b_i * t

与 a_i = sum as above + (1 - i) * c_i和 b_i = c_i .

现在，对于每一次t , 你想找到所有 r_i(t) 中的最大值.为此，我们可以使用函数的排序。具体来说，我们可以对它们进行排序，使函数 f1出现早于 f2在有序序列中 if 函数 f1大于 f2在他们的交点之前。然后，如果我们有给定点的可用函数 t (所有 r_i 都可以在 t 中访问)，我们只需要遍历有序序列。第一个元素将是开始时间的最佳功能。然后，我们可以检查与下一个函数的交集。如果t在那个交叉点之后，我们继续这个函数，因为这将是当前间隔的新最大值。等等。如果您按时间对查询进行排序，则可以为每个查询逐步完成此操作。在执行此过程时，您还需要添加可用的新功能。使用适当的数据结构(例如二叉搜索树)，您可以在 O(log n) 中进行插入。

那么，我们如何比较两个函数 f1(t) = a1 + t * b1和 f2(t) = a2 + t * b2 ？交点是ti = (a2 - a1) / (b1 - b2) .和 f1大于 f2在那之前如果 b1 < b2 .

整体算法如下:

input: n stores, q queries Q
sort queries by time - O(q log q)
create empty BST
currentBestFunction = empty  //pointer to element in BST
nextQuery = Q.first
sumCi = 0   //temporary variable for incremental sum
for t = 1 to maxQ
    if t <= n
        // we can reach a new store
        a = sumCi + (1 - t) * c_t
        b = c_t
        sumCi += c_t
        insert function (a, b) into BST - O(log n)
    if currentBestFunction = empty
        currentBestFunction = the inserted function
    while currentBestFunction is not the last function in BST
        successor = find successor function to currentBestFunction in BST
        calculate intersection ti = (successor.a - currentBestFunction.a) / (currentBestFunction.b - successor.b)
        if ti > t
            break //we are in the interval for the current best function
        else
            currentBestFunction = successor
    loop
    if nextQuery == t
        answer query by evaluating currentBestFunction at t
        advance nextQuery
        if no more queries then stop