时间戳

首页 > 解决方案 > 如何以最佳时间复杂度有效地解决这个问题？

algorithm - 如何以最佳时间复杂度有效地解决这个问题？

问题描述

给定数组中的一组 N 个数字。给定 Q 查询。每个查询包含 1 个数字 x。

对于每个查询，您需要将 x 添加到数组的每个元素，然后报告数组中绝对值的总和。

注意：对阵列的更改是永久性的。有关更多说明，请参见示例。

输入格式

第一行包含 N ，数组中的元素数。下一行包含数组的 N 个空格分隔的整数。下一行包含 Q（查询数）。下一行包含 Q 个空格分隔的整数（数字 x）。

输出格式

对于每个查询，在换行符中输出总和。

约束
1 ≤ N ≤ 500000
1 ≤ Q ≤ 500000
-2000 ≤ 每个查询中的数量 ≤ 2000
-2000 ≤ 数组元素的值 ≤ 2000

样本输入

3
-1 2 -3
3
1 -2 3

样本输出

5
7
6

解释

查询 1 后： [ 0 , 3 , -2 ] => sum = 0 + 3 + 2 = 5

查询 2 后： [ -2 , 1 , -4 ] => sum = 2 + 1 + 4 = 7

查询 3 后： [ 1 , 4 , -1 ] => sum = 1 + 4 + 1 = 6

#include<stdio.h>
#include<stdlib.h>

int main()
{
  int n,*a,q,*aq;
  long int sum=0;
  scanf("%d",&n);
  a=(int*)malloc(sizeof(int)*n);
  for(int i=0;i<n;i++)
    scanf("%d",&a[i]);

  scanf("%d",&q);
  aq=(int*)malloc(sizeof(int)*q);
  for(int i=0;i<n;i++)
    scanf("%d",&aq[i]);

  for(int i=0;i<q;i++)
  {
    for(int j=0;j<n;j++)
    {
        sum+=abs(aq[i]+a[j]);
        a[j]=aq[i]+a[j];
    }

    printf("%ld\n",sum);
    sum=0;

  } 

}

一些测试用例超时。

标签： algorithmperformancelogic

解决方案

您的解决方案正在执行 NQ 操作，这是巨大的。

首先注意数据的范围是适中的，因此您可以使用包含 4001 个条目的直方图来表示 N 个数字。此直方图在 N 次操作中计算（加上初始化 bin）。

然后，请求的总和作为每个 bin 的绝对差之和，由 bin 值加权。这将工作负载从 NQ 降低到 BQ（B 是 bin 的数量）。

如果我是对的，我们可以通过将总和分解为负值的子总和和正值的子和来做得更好。这些和是通过计算前缀和获得的。在 B 操作中预处理直方图之后，这应该会导致 Q 操作中的解决方案。

推荐阅读