2

问题

我需要计算一个整数数组的函数。对于数组的每个三元素子集（或三元组），我需要计算术语 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;
}

有没有更好的优化提示？

4

1 回答 1

0

虽然仍然是 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);
    }
  }
}
于 2016-10-18T20:51:11.027 回答