创建最小成本数组

Question

我有一个大小为n+1的数组，我希望在其中存储购买n个物品的最小成本（第i个索引存储第i个物品的成本）。

有m个不同的卖家：每个卖家提供L到R项目（其中L,R>=1且L,R<=n），每个项目的成本是C。

为了创建最小成本数组，我执行了以下操作:

for (int i=1; i<=m; i++) {
    int L = L of i^th seller
    int R = R of i^th seller
    int C = selling price of i^th seller
    for (int j=L; j<=R; j++) {
        if (leastCost[j]==0 || leastCost[j]>C) {
            leastCost[j]=C
    }
}

构造这个数组的时间复杂度是 O(n*m)，访问这个数组的时间复杂度是O(1)。

对于非常大的 n 和 m 值，有没有更好的方法来构建成本最小的数组呢？

也许可以采用一种不将其存储在数组中的不同方法，以便减少总体时间复杂度？

- Gsquare

---

我不知道你从哪里得到了 O(n^2)。我得到的是 O(n * m)。这是完全不同的。当考虑到你实际需要访问（读取）多少个元素时，这应该是最优的。除非你有任何额外的信息可以开始使用... - Aron

我已经纠正了它。即使对于非常大的n和m，这真的是最优的吗？我没有其他可以添加的了。 - Gsquare

@Aron太高了吗？是的，Aron是正确的。你的卖家表有m个卖家和n个价格（平均值）。因此这是n*m。你至少需要遍历每个元素一次，因此(n*m)是最优的（除非你有量子计算机）。 - xyz

你可以使用线段树，这样时间复杂度将为O(m log n)用于创建树，每个查询将是O(log n)。 - Pham Trung

@Gsquare 最佳的优化方法是使用贪心算法，这也是我在解决方案中展示的。 - Sumeet

Answer 1

你可以在这里使用某种形式的堆栈。

首先按L排序所有卖家，如果L相等，则按C降序排序。

然后从第一个卖家（Li最小）开始。

如果堆栈为空，则将其放入堆栈。如果没有更多的卖家与之匹配，则弹出堆栈顶部元素，并将当前卖家放入堆栈中。

(Lj == Li)

然后 cost[Li] = C[i] 和 Li++（在堆栈中）

如果有一个条目与 Lj == Li 相同，则

• 如果 Rj < Ri 并且 Cj > Ci 则跳过

• 如果 Rj < Ri 并且 Cj < Ci 则将此销售员添加到堆栈中

• 如果 Rj > Ri 并且 Cj > Ci，则弹出当前销售员（i），添加此销售员（j）并添加销售员（i）

- Herokiller

---

我不确定这是如何工作的。你能提供一些可行的代码或更好的伪代码吗？ - Gsquare

Answer 2

肯定的，我们可以做得比O(n*m)更好，而且解决方案非常简单。

以下是解决此问题的伪代码：

Construct a MIN-HEAP of the sellers based on their costs c.

Construct another array x[1...n] with its each element set to 0 initially.

Do the following initializations:
 count=0

while(count < n)
{
 S = EXTRACT_MIN(Heap)
 if(count==0)
 {            
  for(j=S.L to S.R)
  {
   leastCost[j]=S.c
   ++count
   x[j]=S.R
  } 
 }
 else
 {
  for(j=S.L;j<=S.R;++j)
  {
   if(x[j]!=0)
   {
    i=x[j] and continue;
   }
   else 
   {
    leastCost[j]=S.c
    ++count
    x[j]=S.R
   }
  }
 }
}

解释

在这个问题中，我们可以实现的最佳优化是跳过所有已经填充了最小成本的数组索引。

x辅助数组：数组x帮助我们跳过已经填充的所有数组索引，因为：

x [i]存储索引j，使得i到j已经填充了最小成本的数组，这就是使用条件语句的原因：

if(x[i]!=0)
{
 i=x[i] and continue;
}

基本上，它帮助我们直接跳转到未填充的索引处。

MIN-HEAP：它允许我们在时间复杂度为O(logm)的情况下找到所有费用中的最小费用c。

时间复杂度

由于我们最多只会访问leastCost数组n次，因此访问数组的时间复杂度为：O(n)

构建堆需要O(m)的时间

在最坏的情况下，所有卖家都将对某些索引做出贡献，并且将有确切的m个EXTRACT_MIN(Heap)操作，每个操作需要O(logm)的时间，因此这个过程的时间为：O(m*logm)。

因此，总时间复杂度=O(n+mlogm+m)=O(n+mlogm)。

顺便说一句，如果我使用C语言，我会为Seller使用struct，如果是Java，则为Seller使用class。如有任何问题，请随时提出。

- Sumeet

---

@PhamTrung，请允许我解释一下您的疑惑。每当内部循环被执行时，它都会递增控制外部循环的变量，即计数变量。这就是导致我的时间复杂度的原因。 - Sumeet

@PhamTrung 嵌套循环并不总是意味着二次时间复杂度。只有当控制内部和外部循环的变量彼此独立时，才会出现二次时间复杂度。 - Sumeet

我明白了，但是你如何处理这种情况？(5, 5, 1)，(4, 5, 2)，(3, 5, 3)....(1, 5, 5)，(5, 6, 7)....(5, 10, 10)。其中n=10，每个销售员都表示为(L, R, C)。显然，总时间复杂度将为2 *（1 + 2 + ... + n / 2）= O(n^2)，因为在每次迭代中，您只能更新一项，并且仍需要遍历所有范围。 - Pham Trung

时间复杂度对于上述情况确切地为 O(n^2 log m)，其中 n/2 的求和公式为 2*(1 + 2 + ... + n/2)，m 为常数。 - Pham Trung

@PhamTrung 请重新审视你的基础知识。Big O 是用于渐近分析的符号，而不是你在表达式中计算的内容。 - Sumeet

让我们在聊天中继续这个讨论。 - Sumeet

Answer 3

这个问题是一个经典问题 区间最小值查询, 你可以使用 线段树 来获取一个时间复杂度为 O(m log n) 的解决方案，其中创建树的时间复杂度为O(m log n)，每个查询的时间复杂度为O(log n)。

更多细节:

我们使用一棵树来表示从1到n每个物品的最小价格。

对于每个卖家，我们会更新这棵树：

tree.update(L, R, C);

最后，为了获取项目i的最小值，我们查询树：

tree.getMin(i, i);

由于update和getMin的时间复杂度均为O(log n)，因此整个程序的时间复杂度为O(max(m,n) log n)。您不需要修改原始线段树实现中的任何内容。

- Pham Trung

---

我没有范围查询。我该如何为这种特殊情况构建线段树？ - Gsquare

@Gsquare：每个卖家都提供从物品L到物品R的项目。从L到R，更新值C（如果可能），这些是范围查询。对于每个项目i，查询是获取范围（i，i）的最小值，其时间复杂度为O(log n)。 - Pham Trung