Недавно я столкнулся с этой проблемой на codeforces.com. Высказывание интересное и короткое. Вам дан массив размера N, теперь ваша задача состоит в том, чтобы найти два индекса i и j, такие что i ‹ j, A[i] ‹ A[j] и A[i] * A[j] минимально, как возможно во всех возможных действительных парах. Поскольку решение O(N²) прямолинейно, мы обсудим, как решить его за O(N).
Окончательное состояние ответа зависит от того, является ли ответ положительным или отрицательным, поэтому мы разделим ответ на три случая и решим индивидуально для каждого.
- Ответ отрицательный, поэтому A[i] * A[j] ‹ 0 для оптимально выбранных i и j.
В этом случае решить несложно, так как отрицательным может быть только один элемент, из чего следует, что это должен быть A[i], так как A[i] ‹ A[j] из условий задачи. Решить это просто, нам нужно поддерживать минимум префикса во всем массиве, тогда для каждого элемента A[i] он может внести свой вклад в вышеуказанный случай, если и только если prefix_minimum[i] * A[i] ‹ 0, тогда для всех действительных индексов, нам нужно минимизировать ответ по prefix_minimum[i] * A[i], где prefix_min[i] равен минимуму(prefix_minimum[i — 1], A[i]).
2. Ответ положительный, при A[i] ≥ 0 и A[j] ≥ 0 для оптимально выбранных i и j.
Этот случай также легко решается, для каждого элемента нам просто нужно минимизировать по A[i] * prefix_min[i], если A[i] > prefix_min[i].
3. Ответ положительный, с A[i] ‹ 0 и A[j] ‹ 0, для оптимально выбранных i и j.
Это действительно интересный случай, так как оба числа отрицательные, мы должны жадно пытаться умножить числа с минимальным абсолютным значением. Например, умножение -3 на -2 более полезно, чем, скажем, умножение -20 и -25, хотя -3 и -2 — большие числа. Это приводит к тому, что жадный подход, используемый в случаях №1 и №2, не дает оптимального решения.
Давайте попробуем пойти с другой стратегией, мы можем заметить, что как только отрицательное число A[j] появляется в массиве, никогда не будет выгодно соединять любой элемент меньше A[j] в позиции ‹ j с любым элементом после j . Более формально обозначим наши индексы как i, j и k, где i ‹ j ‹ k, A[i] ‹ A[j] и A[i], A[j], A[k] ‹ 0. Тогда A[k] * A[j] ‹ A[i] * A[k] для всех k.
Другими словами, мы должны попытаться сопоставить каждый индекс с каждым еще не совпавшим индексом слева от него, который меньше его. На первый взгляд это выглядит как O(N²), но при тщательной реализации мы можем достичь O(N) за амортизированное время. Мы будем использовать монотонный стек (стек, в котором каждое значение увеличивается снизу вверх). Перед тем, как поместить элемент в стек, мы продолжаем извлекать каждый элемент, меньший, чем он, и минимизируем по этой паре, в противном случае мы останавливаемся и помещаем этот элемент. По сути, мы моделируем идею из предыдущего абзаца. Это интеллектуальный метод грубой силы, сочетающий жадность с перебором только потенциально интересных пар.
Вот фрагмент:
stack<int> stack;
for (int i = 0 ; i < N; ++i) {
int currentElement = A[i];
// skip current iteration if currentElement is not less than 0
while (!stack.empty() && stack.top() < currentElement) {
answer = minimum(answer, stack.top() * currentElement);
stack.pop();
}
stack.push(currentElement);
}
Если вы хотите попробовать эту задачу, она здесь: https://codeforces.com/contest/1090/problem/I.
Вам все еще нужно построить массив с помощью генератора, вот спойлер о том, как это сделать эффективно, вы можете использовать тип данных unsigned int для вашего массива.
