Как найти наибольшее умножение между числами в заданном массиве (предел 100000 чисел)
Я пытаюсь изучать программирование, и в нашей школе есть упражнения, которые автоматически проверяются ботом. Ограничение по времени — 1 секунда, а ограничение по памяти — 1024 Мб. Я попытался отсортировать массив в порядке возрастания, а затем умножить 2 самых высоких числа, но это было слишком медленно (мой алгоритм сортировки может быть медленным, поэтому, если возможно, предложите алгоритм сортировки.) Это самый быстрый способ, который я смог сделать:
#include <iostream>
#include <fstream>
#include <iomanip>
using namespace std;
int Maksimumas(int n, int X[]);
ofstream fr("U1rez.txt");
ifstream fd("U1.txt");
int main()
{
int n, A[100000], B[100000], maxi=0;
fd >> n;
for (int i = 0; i < n; i++) {
fd >> A[i];
}
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
B[j] = A[i] * A[j];
}
maxi = Maksimumas(n, B);
A[i] = B[maxi];
}
maxi = Maksimumas(n, A);
fr << A[maxi];
fr.close();
return 0;
}
int Maksimumas(int n, int X[])
{
int maxi = 0;
for (int i = 0; i < n; i++) {
if (X[maxi] < X[i]) {
maxi = i;
}
}
return maxi;
}
n - размер массива для всех, кто интересуется.
Попробуйте использовать std::nth_element.
Что еще вы предлагаете? Текущий самый быстрый метод, который я придумал (который все еще слишком медленный, должен быть примерно в 4 раза быстрее). Этот метод никаким образом не сортирует массив, он просто использует массив для умножения и помещает результат умножения во второй массив. Мне действительно нужна помощь, чтобы оптимизировать мой код для этой проблемы. Я хочу стать лучше в программировании.
сортировка O(N * logN), в то время как для нахождения максимального и второго максимального числа необходим только один проход по массиву.
Как бы вы предложили найти 2-й максимум, если предположить, что это может быть одно и то же число? Я не знаю, как решить такую проблему
Я имею в виду, когда вы найдете новый максимум, что вы сможете сделать со старым максимумом?
Ответы 1
Вам не нужно сортировать весь массив — вам просто нужны два самых больших положительных числа и два самых маленьких отрицательных числа. Все, что между ними, не имеет значения.
Вместо этого вы можете просмотреть весь ввод и отследить два самых больших положительных числа и два самых маленьких отрицательных числа.; В конце итерации умножьте каждую пару (если она найдена) и сравните результаты.
// fd is opened like the original question, n is the number of elements to read
// that part is omitted for brevity
int max = -1;
int preMax = -1;
int min = 1;
int preMin = 1;
int temp;
for (int i = 0; i < n; i++) {
fd >> temp;
if (temp > preMax) {
if (temp > max) {
preMax = max;
max = temp;
} else {
preMax = temp;
}
} else if (temp < preMin) {
if (temp < min) {
preMin = min;
min = temp;
} else {
preMin = temp;
}
}
}
int result = -1;
if (preMax >= 0) {
result = preMax * max;
}
if (preMin <= 0) {
int tempResult = preMin * min;
if (tempResult > result) {
result = tempResult;
}
}
return result;
Вы находите как максимумы, так и минимумы, помещая числа в массив?
@emirisu нет, я не трачу память на массив - я просто отслеживаю два самых больших положительных и два самых маленьких отрицательных значения.
Спасибо за помощь! У меня наконец-то получилось :). Мне все еще нужно было добавить некоторые команды if, чтобы код работал, если n меньше 4, и все же, если бы не ваше предложение, я, вероятно, не нашел бы решения.
Если вы хотите найти максимальное и второе максимальное число, вам действительно нужно сортировать весь массив?