1
У меня есть два массива:Как это эффективно решить?
score[n]pos[n], где п = < 10^5; поз [я], оценка [я] < = 10^4
Определение:
f(i,j) = abs(pos[i]-pos[j])*max(score[i],score[j])
Мне нужно найти сумму f(i,j) для всех i,j с.
У меня есть алгоритм, который может решить его в O(n^2), но я хочу оптимизировать.
Я потратил много времени, но не смог.
Любая помощь приветствуется. Худший код случая http://ideone.com/q4qSNh
Можете ли вы предоставить фрагмент или фрагменты кода для лучшего контекста, пожалуйста? – ganjeii
Ваша функция f симметрична по i и j, то есть f (i, j) = f (j, i), поэтому простая оптимизация состоит в том, чтобы оценивать только треугольник и затем удваивать результат. Тем не менее O (n^2), но только половина усилия. – Henry
Я подумал, что – prem