sum — Оптимизация суммирования триплета в переполнении стека

Question

sum — Оптимизация суммирования триплета в переполнении стека

проблема

Мне нужно вычислить функцию массива целых чисел. Для каждого трехэлементного подмножества (или триплета) массива мне нужно вычислить термин floor ((сумма триплета) / (произведение триплета)). Тогда мне нужно вернуть сумму всех таких терминов.

пример

Вход (длина; массив):

5
1 2 1 7 3

Выход:

объяснение

В данном массиве существуют следующие триплеты:

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, потому что этаж ((1 + 2 + 1) / (1 * 2 * 1)) = этаж (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;
}

Есть ли намек на лучшую оптимизацию?

2

c++sum triplet

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Пока 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);
}
}
}

0