Нужно найти 2 элемента, произведение которых максимально в vector'е на С++

Question

На вход программе сначала подается значение n≤50000 — количество элементов в массиве. В следующей строке входных данных расположены сами элементы массива — целые числа, по модулю не превосходящие 30000.

Примеры:

Ввод

5

-4 3 -5 2 5

Вывод

-5 -4

Я взял часть кода с одного сайта и подстроил под vector.

#include <vector>
using namespace std;
int main()
{
   int n, max1 = -30001, max2 = max1, min1 = 30001, min2 = min1;
   cin >> n;
   vector<int> a(n);
   for (int i = 0; i < n; i++)
   {
       cin >> a[i];
       if (a[i] < min1) { min2 = min1; min1 = a[i]; }
       else if (a[i] < min2) min2 = a[i];
       if (a[i] > max1) { max2 = max1; max1 = a[i]; }
       else if (a[i] > max2) max2 = a[i];
   }
   if (min1 * min2 > max1 * max2) cout << min1 << " " << min2;
   else cout << max2 << " " << max1;
   return 0;
}

У меня есть предположение, что проблема в нахождении min и maх, но не понимаю в чем конкретно и как это сделать по-нормальному

Answer 1

Максимальное число в Вашем случае можно получить умножив два самых больших числа или два самых маленьких, если они оба отрицательные. Поэтому, делаем так

sort(v.begin(), v.end());
if (v.size() < 2) return "ups";// нет даже двух элементов:) обработайте так, как Вам нравится
int m1 = v[0] * v[1];
int m2 = v[v.size()-1] * v[v.size()-2];
if (m1 > m2) return m1 else return m2;

Но у этого алгоритма есть одна "проблема" - его сложность - n * ln(n). Это может быть много. Но тут появляется условие "по модулю не превосходящие 30000". Значит можно завести массив на 30000*2 элементов типа char (а если подумать, то и по два бита на каждое число хватит).

vector<char> v{0};
v.resize(60001);

для каждого числа n просто увеличиваем в массиве элемент с индексом n-30001. Паралельно проверяем, что не превысили лимита (а то если кол-во элементов будет равно 256 - будет снова ноль).

Когда все числа пройдем, можно просто и легко найти максимальные и минимальные элементы. Вот тут нам и пригодится то, что считали кол-во - ведь нам нужны два самых больших (маленьких) числа, а не два разных числа.

Answer 2

Решение, в Сириусе проходит. Если Вы тоже проходите курс Информатика.Юниоры 2021, то заходите в беседу https://t.me/joinchat/EXKcUAW4bZE3NTFi

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; i++)
        cin >> v[i];

    int a, b, c, d;
    a = c = v[0];
    b = d = v[1];
    if (a > b)
        swap(a, b);
    if (c > d)
        swap(c, d);
    for (int i = 2; i < n; i++) {
        if (v[i] > a) {
            if (a > b)
                b = a;
            a = v[i];
        } else if (v[i] > b)
            b = v[i];

        if (v[i] < c) {
            d = c;
            c = v[i];
        } else if (v[i] < d)
            d = v[i];
    }
    if (a > b)
        swap(a, b);
    if (c > d)
        swap(c, d);
    if (a * b > c * d)
        cout << a << " " << b;
    else
        cout << c << " " << d;
}

Answer 3

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
  int n;
  std::cin >> n;
  std::vector<int> arr(n);
  for (int i = 0; i < n; ++i) {
    std::cin >> arr[i];
  }

  std::sort(arr.begin(), arr.end());

  int maxProd = arr[0] * arr[1];
  int maxFirst = arr[0];
  int maxSecond = arr[1];

  for (int i = 1; i < n-1; ++i) {
    int currProd = arr[i] * arr[i+1];
    if (currProd > maxProd) {
        maxProd = currProd;
        maxFirst = arr[i];
        maxSecond = arr[i+1];
      }
  }

  std::cout << maxFirst << " " << maxSecond << std::endl;

  return 0;
}

БЛОГ НА HUSL

Нужно найти 2 элемента, произведение которых максимально в vector'е на С++

Ответы (3 шт):