c++ - 找到包含 200000+ 个元素的 2 个数组元素的最小乘积的最快方法

Question

我有一个数组 a[n] .号码n是我们输入的。我需要找到 a[i] 的最小乘积和 a[j]如果:

1) abs(i - j) > k
2) a[i] * a[j]最小化

这是我的解决方案(非常幼稚):

#include <iostream>
using namespace std;
#define ll long long
int main() {
    ll n,k; cin >> n >> k;

    ll a[n]; for(ll i=0;i<n;i++) cin >> a[i];

    ll mn; bool first = true;

    for(ll i=0;i<n;i++) {
        for(ll j=0;j<n;j++) {
            if(i!=j)
            if(abs(i-j) > k) {
                if(first) {
                    mn = a[i]*a[j];
                    first = false;
                } else if(a[i]*a[j] < mn) mn = a[i]*a[j];
            }
        }
    }
    cout << mn << endl;
}

但是我想知道是否有任何更快的方法可以找到具有距离的最小乘积？

Answer 1

假设至少有一对元素满足条件并且其中两个元素的乘法没有溢出，这可以在 Theta(n-k) 中完成。时间和Theta(1)空间最坏和最好的情况，如下所示:

auto back_max = a[0];
auto back_min = a[0];
auto best = a[0]*a[k+1];

for(std::size_t i=1; i<n-(k+1); ++i) {
    back_max = std::max(back_max, a[i]);
    back_min = std::min(back_min, a[i]);
    best = std::min(best, std::min(a[i+k+1]*back_max, a[i+k+1]*back_min));
}

return best;

这在时间和空间的渐近最坏情况复杂度方面是最佳的，因为最佳乘积可能是 a[0]与任何 n-(k+1)元素距离至少 k+1 ，所以至少 n-(k+1)任何解决问题的算法都需要读取整数。

该算法背后的思想如下:

最优乘积使用 a的两个元素，假设这些是 a[r]和 a[s] .不失一般性，我们可以假设 s > r因为乘积是可交换的。

由于限制 abs(s-r) > k这意味着 s >= k+1 .现在 s可能是满足此条件的每个索引，因此我们迭代这些索引。这是对 i 的迭代在显示的代码中，但它被移动了 k+1为了方便(并不重要)。对于每次迭代，我们需要找到涉及 i+k+1 的最优产品。作为最大指数，并将其与之前的最佳猜测进行比较。

配对的可能索引 i+k+1所有索引都小于或等于 i由于距离要求。我们还需要迭代所有这些，但这是不必要的，因为最小值 a[i+k+1]*a[j]在 j在固定 i等于 min(a[i+k+1]*max(a[j]), a[i+k+1]*min(a[j]))由于产品的单调性(在 a[j] 上取最小值和最大值的最小值解释了 a[i+k+1] 的两个可能的符号或等效的两个可能的单调方向。)

自集 a[j]我们在这里优化的值只是 {a[0], ..., a[i]} ，它在 a[i] 的每次迭代中仅增长一个元素( i ) ，我们可以简单地跟踪 max(a[j])和 min(a[j])如果 a[i]，则通过更新它们来使用单个变量大于或小于先前的最佳值。这是通过 back_max 完成的和 back_min在代码示例中。

迭代的第一步( i=0 )在循环中被跳过，而是作为变量的初始化执行。