c++ - 优化 C++ 中的三元组求和

Question

问题

我需要计算一个整数数组的函数。对于数组的每个三元素子集(或三元组)，我需要计算术语 floor((三元组之和)/(三元组乘积))。然后我需要返回所有这些项的总和。

例子

输入(长度；数组):

5
1 2 1 7 3

输出:

6

解释

给定数组中存在以下三元组:

1 2 1

1 2 7

1 2 3

1 1 7

1 1 3

1 7 3

2 1 7

2 1 3

2 7 3

1 7 3

考虑样本输入中的这些三元组:

1 2 1 贡献 2，因为 floor((1+2+1)/(1*2*1)) = floor(4/2) = 2

1 2 3 贡献 1

1 1 7 贡献 1

1 1 3 贡献 1

2 1 3 贡献 1

所有其他三元组对总和的贡献为 0。

因此答案是(2+1+1+1+1)=6。

我的解决方案

我尝试的是复杂度 O(n^3)。代码如下:

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
    long t,n[300005],sum=0,mul=1,i,j,k,res=0;
    cin >> t;

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


    for(i=0;i<t-2;i++)
    for(j=i+1;j<t-1;j++)
    for(k=j+1;k<t;k++)
    {
        sum = n[i]+n[j]+n[k];
        mul = n[i]*n[j]*n[k];
        res += floor(sum/mul);
    }

    cout << res << endl;
    return 0;
}

有没有更好的优化提示？

Answer 1

虽然仍然是 O(n^3)，但您可以通过在迭代时缓存 n[i] 和 n[j] 之间的冗余计算来节省一些操作n[k].

例如:

long sum_ij,mul_ij;

for(i=0;i<t-2;i++) {
  for(j=i+1;j<t-1;j++) {

    sum_ij = n[i]+n[j];
    mul_ij = n[i]*n[j];

    for(k=j+1;k<t;k++)
    {
       sum = sum_ij+n[k];
       mul = mul_ij*n[k];
       res += floor(sum/mul);
    }
  }
}