У меня есть массив 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;
}
Но я хочу знать, есть ли более быстрый способ найти минимальный продукт с расстоянием?
c++
algorithm
optimization
minimum
Mouvre
источник
источник
std::vector
? @Scheff - сортировка разрушила бы исходные «дистанционные» отношения.if (i!=j) if (abs(i - j) > k)
может быть устранена. Просто начните внутреннюю петлю I + к + 1:for (ll j = i + k + 1; j < n; ++j)
. Проверка с помощьюfirst
может быть также отменена, еслиmn
инициализирована до, например, сmn = a[0] * a[k + 1];
. (Можетk
быть,n
сначала нужно проверить, чтобы сделать это пуленепробиваемым.) Но это все равно O (N²). Это должно быть выполнимо быстрее ...Ответы:
Предполагая, что есть хотя бы одна пара элементов, удовлетворяющих условиям, и нет умножения двух элементов в ней, переполнения, это может быть сделано во
Theta(n-k)
времени иTheta(1)
пространстве в наихудшем и наилучшем случае, с чем-то вроде этого:Это оптимально с точки зрения асимптотической сложности в худшем случае как для времени, так и для пространства, поскольку оптимальным произведением может быть как минимум
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
) пропускается в цикле и вместо этого выполняется как инициализация переменных.источник
a[i+k+1]
являются минимум и максимум.Не уверен насчет самого быстрого .
Для более простой задачи без i <j - k минимальное произведение находится среди произведений пар из двух наименьших и самых больших элементов.
Итак, (следующее слишком сложно, см . Ответ грецкого ореха )
(• прекратить, если k ≤ n
• инициализировать minProduct a [0] * a [k + 1])
начиная с {} и {a [ j ] | k ≤ j }
min ( upToI ) × min ( beyondIplusK ), min ( upToI ) × max ( beyondIplusK ),
max ( upToI ) × min ( beyondIplusK ) и max ( upToI ) × max ( beyondIplusK )
источник
minUpto
,maxUpto
,minBeyond
,maxBeyond
(Вы можете создать в двух итераций)? Затем на третьей итерации для каждого индекса найдите минимально возможное умножение.Для «минимальной величины»
Найдите 2 элемента «наименьшей величины», затем (после того, как вы нашли два нуля или произвели поиск по всему массиву), умножьте их.
Для «наименьшего значения» без
abs(i - j) > k
деталиЕсть 3 варианта:
два старших (наименьшей величины) отрицательных числа
два наименьших (наименьшей величины) неотрицательных числа
наименьшее (наибольшая величина) отрицательное число и наибольшее (наибольшая величина) неотрицательное число
Вы можете найти все 6 значений и выяснить, какие продукты являются лучшими в конце.
Однако; как только вы видите ноль, вы знаете, что вам больше не нужно знать о первых двух возможностях; и как только вы видите одно отрицательное число и одно неотрицательное число, вы понимаете, что вам важна только третья возможность.
Это приводит к конечному автомату с 3 состояниями - «заботиться обо всех 3 возможностях», «ответ равен нулю, если не видно отрицательное число» и «заботится только о последней возможности». Это может быть реализовано как набор из 3 циклов, где 2 цикла переходят (
goto
) в середину другого цикла, когда состояние (конечного автомата) изменяется.В частности, это может выглядеть примерно так (не проверено):
Для "наименьшего значения" с
abs(i - j) > k
частьюВ этом случае у вас все еще есть 3 возможности; и может заставить его работать с тем же подходом «3 цикла с конечным автоматом», но он становится слишком грязным / безобразным. В этом случае лучшей альтернативой может быть предварительное сканирование массива, чтобы определить, есть ли нули и все ли они отрицательные или все положительные; так что после предварительного сканирования вы можете узнать, что ответ равен нулю, или выбрать цикл, предназначенный только для конкретной возможности.
источник