C/C++

Задача на максимальное произведение в векторе C++ Где ошибка в коде?

Задача: Максимальное произведение
В массиве, заполненном произвольными целыми числами, найдите два числа, произведение которых максимально. Вложенные циклы не используйте.

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

Выдайте два искомых числа в порядке неубывания.

Код:
```

 #include 

#include 

using namespace std;



int main(){

  long long n, maxin = -1, ans, ans2;

  cin >> n;

  vector  v(n);

  // Цикл для считывания вектора

  for (int l = 0; l < n; l+=1){

    cin >> v[l];

  }

  // Цикл для сравнения

  for (int i = 0; i
MS
Marchelo_1965 Saund
324
Тебе в задании прямым русским языком сказали: "Вложенные циклы не используйте". И ты тут же пишешь код со вложенными циклами.

50000 * 50000 = 2 500 000 000: ты своим вложенным циклом делаешь два с половиной МИЛЛИАРДА сравнений.
Разумеется, времени не хватает.

А всего-то надо проверить комбинации 4 чисел: двух максимальных и двух минимальных (-100 * -99 больше, чем 97 * 98).

Простейшее решение - использовать сортировку. Быстрая сортировка для 50000 элементов потребует в 3000 меньше сравнений, чем твой перебор всех комбинаций.
 long n;

cin >> n; 

vector v(n);



// Цикл для считывания вектора 

for (auto &a : v){ cin >> a; }



// Данных слишком мало для получения ответа

if (n < 2) {

  cout  v[i] * v[j]) {

  i = 0;

  j = 1;

}

if (v[0] * v[n - 1] > v[i] * v[j]) {

  i = 0;

  j = n - 1;

}



cout
Москва Москва
Москва Москва
76 358
Лучший ответ
Александр Филиппов Никак не могу понять смысл второго if. В каком массиве максимальным будет произведение минимального и максимального элементов? 
 #include  

#define min(a,b) ((a)>(b)?(b):(a)) 

#define max(a,b) ((a)>(b)?(a):(b)) 

using namespace std; 

 

class mima 

{ 

    int min1, min2; 

    int max1, max2; 

    char valid_min; 

    char valid_max; 

public: 

    mima() :min1(INT_MAX), min2(INT_MAX), max1(INT_MIN), max2(INT_MIN),valid_min(2),valid_max(2) {}; 

    friend istream& operator >> (istream&, mima&); 

    pair get() 

    { 

        double min_de = min1*min2, max_de = max1*max2; 

        if (!valid_max && !valid_min) return min_de > max_de ?  

            pair{ true,pair{ min(min1,min2),max(min1,min2)}} : pair{true,pair{min(max1,max2),max(max1,max2)}}; 

        if (!valid_max) return pair{ true,pair{ min(max1,max2),max(max1,max2) } }; 

        if (!valid_min) return pair{ true,pair{min(min1,min2),max(min1,min2) } }; 

        if (valid_min == 1 && valid_max == 1) return pair{ true,pair{ min(min1,min2),max(max1,max2) } }; 

        return pair{ false,pair{0,0} }; 

    } 

}; 

istream& operator >> (istream& in, mima& mum) 

{ 

    int val; 

    in >> val; 

    if (val > 0 && min(mum.max1, mum.max2) < val) 

    { 

        min(mum.max1, mum.max2) = val; mum.valid_max >>= 1; 

    } 

    else if (max(mum.min1, mum.min2) > val)  

    { 

        max(mum.min1, mum.min2) = val; mum.valid_min >>= 1;  

    }; 

    return in; 

} 

 

int main() 

{ 

    mima muma; 

    size_t n; 

    cin >> n; 

    while (n--) cin >> muma; 

    if (muma.get().first) cout
Александр Савишкин
Александр Савишкин
51 417

Похожие вопросы