获得左半积和右半积的绝对差最小的元素 [英] Get the element for which the absolute difference between left half product and right half product is minimum

问题描述

我想找到给定数组中的元素（n个元素），使得左半部乘积和右半部乘积之间的绝对差最小

I want to find the element in a given array (n elements) such that the absolute difference between the left half product and the right half product is minimum

(abs(arr[0]*arr[1]*...arr[x]-arr[x+1]*arr[x+2]...arr[n]))

该问题还会定期 m次更新数组的值。我想获取O（m log n）中所有查询的答案。

the question also updates the values of the array regularly 'm' times. I want to get answers of all queries in O(m log n).

我尝试了一种耗时O（n * m）且无法正常工作的方法

I have tried an approach which takes O(n*m) time and it is not working due to TLE error.

推荐答案

我想到的唯一方法是：

如此大的数字很难相乘。

Multiplication of such a big number is hard.

我们可以将其隐瞒为

log10（A [1] A [2] ... * A [x]）-log10（A [x + 1] A [x + 2] .. * A [n]）

log10（A [1]）+ log10（A [2]）+ .. + log10（A [x]） -log10（A [x + 1]）+ log10（A [x + 2]）+ .. + log10（A [n]）

log10(A[1]A[2]...*A[x])- log10(A[x+1]A[x+2]..*A[n])
log10(A[1])+log10(A[2])+..+log10(A[x])-log10(A[x+1])+log10(A[x+2])+..+log10(A[n])

现在这些结果可存储为两倍。

Now these result are storable in double.

以abs（（A [1] A [2] ... * A [x]）-（A [x + 1] A [x + 2] .. * A [n]））应该最小化，
这个等式将遵循三元搜索。

As abs((A[1]A[2]...*A[x])- (A[x+1]A[x+2]..*A[n])) should be minimized, this equation will follow the rules of ternary search.

因此，在三元搜索的每次迭代中，我们都需要

So in each iternation of ternary search we need the result of

log（A [1]）+ log（A [2]）+ .. + log（A [x]）

和

log（A [x + 1]）+ log（A [x + 2]）+ .. + log（A [n]）

log(A[1])+log(A[2])+..+log(A[x])
and
log(A[x+1])+log(A[x+2])+..+log(A[n])

由于进行了一些更新，我们需要一种数据结构来查找具有较低
复杂度（例如分段树）的数据结构。

As there is some update, we need a data structure for finding them with lower complexity like segment tree.

因此，总体复杂度将为log（n）*每个查询的日志（n）。

So overall complexity will be log(n)*log(n) for each query.

这篇关于获得左半积和右半积的绝对差最小的元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！