创建最低成本数组

Question

我有一个大小为n + 1的数组,我希望存储购买n物品的最低成本(i^th索引商店的i^th物品成本).

有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,是否有更好的方法来构建成本最低的数组？

也许是一种不将其存储在数组中的不同方法,以及其他方面可以减少整体时间复杂度？

Answer 1

当然，我们可以做得比 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。

时间复杂度

由于我们最多访问数组 lessCost n 次，因此访问数组：O(n)

构建堆需要O(m)

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

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

顺便说一句，如果我使用 C 语言，我会使用 struct 作为 Seller，如果是 Java，则使用类作为 Seller。如有任何查询，请随意。