arrays - 更新范围内数组的值

Question

我有一个数组 [1:N]，它被初始化为 MAXIMUM-VALUE。

我必须维护一个系统，在该系统中，每个用户/投标人都给出元素的范围(低、高)及其对该范围内每个元素的出价。他对这个范围内的每个元素的出价都是一样的。我必须为所有不同的元素获得最低出价。在一些出价之后，我必须获得数组的值。

我写了一段代码，但它的运行时间复杂度为 O(n^2)。

while(number_of_bids--)
{
    cin>>low>>high>>bid_value;
    while(low<=high && low<=N)
    {   
        vs[low].cost=min(vs[low].cost,bid_value);
        low++;
    }
}

例如，如果数组[1:10]，出价是:

1 2 65
2 4 58
3 7 86
1 9 88

然后数组的值变为:

65, 58, 58, 58, 86, 86, 86, 88, 88, MAXIMUM-VALUE

请提出任何可以提高时间复杂度的算法。

Answer 1

您可以通过使用索引的结构和映射来实现。这是解释:首先构建范围和出价结构的数组/向量。作为:

struct node{
 int bid;
 int left;
 int right;
}arr[10005];

现在在数组中输入出价。然后使用比较器对数组进行排序。如:

sort(arr,arr+n,comp)
// comparator function could be as :
bool comp(node c,node d)
{
return c.bid<d.bid;
} 

现在创建一个用于映射索引的辅助数组并用-1 初始化它。然后遍历结构体数组，将辅助数组填入右边的编号。作为:

int flag=0,count=0;
for(int i=0;i<n;i++){
 flag=arr[i].left;
 while(flag<n && flag<=arr[i].right){
 if(aux_array[flag]==-1){
   aux_array[flag] = arr[i].right;
  flag++;count++;
  }
  else {
     flag=aux_array[flag]+1;
   }
   if(count>=n) break;
  }
 if(count>=n) break;
}

现在，你已经完成了。