Последовательности чисел: как улучшить / ускорить алгоритм?

@Nemovok · Регистрация: 30.10.2015

Студворк — интернет-сервис помощи студентам

Задание:

Кликните здесь для просмотра всего текста

Для заданной последовательности неотрицательных целых чисел необходимо найти максимальное произведение
двух её элементов, номера которых различаются не менее чем на 8. Значение каждого элемента последовательности не
превышает 1000. Количество элементов последовательности не превышает 10000.

Входные данные представлены следующим образом. В первой строке задаётся число N — общее количество элемен‐
тов последовательности. Гарантируется, что N > 8. В каждой из следующих N строк задаётся одно неотрицательное целое
число – очередной элемент последовательности.

Решение:

Кликните здесь для просмотра всего текста

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <vector>
 
void max(int& result, std::vector<int>& vec)
{
  result = std::max(result, vec.front() * vec.back()); 
}
 
int main()
{
  int amount, result = 0;
  std::vector<int> vec(10);
 
  std::cin >> amount;
 
  // Заполняю постой вектор 10-ю элементами
  for (auto& i : vec) 
    std::cin >> i;
 
  // Сравниваю
  max(result, vec);
 
  for (size_t i = 0; i < amount - 10; ++i) {
    // Удаляю первый элемент со смещением назад 
    vec.erase(vec.begin(), vec.begin() + 1); 
  
    // Добавляю новый элемент в конец
    std::cin >> amount;
    vec.push_back(amount);
 
    // Сравниваю 
    max(result, vec);
  } 
 
  std::cout << std::endl << result << std::endl;
 
  return 0;  
}

@rikimaru2013 · 15.01.2017, 00:58

как улучшить

1. Что за магическое число 10?
2. удаление первого элеммента в векторе - всегда очень плохо
3. зачем постоянно вводить и пушить в вектор количество amount?

ускорить алгоритм

1. Что насчёт сортировки последовательности? Сохраним всё в контейнер где будет пара индекс+число. Отсортировали и решили задачу

@Nemovok · 15.01.2017, 01:02 **[ТС]**

Сообщение от rikimaru2013

1. Что за магическое число 10?

10 т.к разница между первым и последним числом 8.

Сообщение от rikimaru2013

2. удаление первого элемента в векторе - всегда очень плохо

Почему? Сложность же O(n).

Сообщение от rikimaru2013

3. зачем постоянно вводить и пушить в вектор количество amount?

А как мне добавить в вектор новое, введенное пользователем число? amount - это не количество

Я просто использовал эту переменную)

@rikimaru2013 · 15.01.2017, 01:04

Сообщение от Nemovok

10 т.к разница между первым и последним числом 8.

Убирайте эти числовые литералы не понятные

Сообщение от Nemovok

Почему? Сложность же O(n).

А с конца O(1) - так зачем платить больше? И вообще зачем что-то удалять?

Сообщение от Nemovok

А как мне добавить в вектор новое, введенное пользователем число?

Я не могу найти в задании, что числа вводяться кажду итерацию. С чёго вы это взяли?

@Nemovok · 15.01.2017, 01:13 **[ТС]**

Прошу прощения, я не привел пример

Пример входных данных:
10
100
45
55
245
35
25
10
10
10
26
Программа должна вывести одно число — описанное в условии произведение. Пример выходных данных для при‐
ведённого выше примера входных данных: 2600.

Добавлено через 1 минуту

Сообщение от rikimaru2013

И вообще зачем что-то удалять?

Экономим память.

Добавлено через 1 минуту
Программа считается эффективной по времени, если время работы программы пропорционально количеству элемен‐
тов последовательности N, т.е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k
раз.
Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных,
не зависит от числа N и не превышает 1 килобайта

@Dimension · 15.01.2017, 01:51

помню в его подобное встречалось

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    int N,x;
    int Max = -1,Mx=-1;
    cin >> N;
    vector<int> a(8);
    for (int i = 0;i < 8;i++)
        cin >> a[i];
    for (int i = 8;i < N;i++)
    {
        cin >> x;
        Mx = max(Mx, a[i % 8]);
        Max = max(max(a[i % 8] * x,Mx*x), Max);
        a[i % 8] = x;
    }
    cout << Max;
    return 0;
}

@rikimaru2013 · 15.01.2017, 13:19

Dimension, а у вас то что делает маг число 8 ?) Вы что сговорились?)

@GbaLog- · 15.01.2017, 13:23

Сообщение от Nemovok

номера которых различаются не менее чем на 8.

Сообщение от rikimaru2013

а у вас то что делает маг число 8 ?)

Думаю, храним каждые 8 элементов.
В теме не разбирался, если что.

P.S. Есть такая штука, называется std::deque, я слышал легенду о том, что там удаление с конца и с начала за О(1).

@Dimension · 15.01.2017, 14:23

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

@rikimaru2013 · 15.01.2017, 14:32

Dimension, я всего лишь про магическое число. Думаю самое время загуглить это понятия и понять что я пытаюсь вам донести. Как думаете?

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@rikimaru2013 2549 / 1208 / 358 Регистрация: 30.11.2013 Сообщений: 3,826
	15.01.2017, 13:19
	Dimension, а у вас то что делает маг число 8 ?) Вы что сговорились?) 0

@Dimension Dimension 595 / 463 / 223 Регистрация: 08.04.2014 Сообщений: 1,710
	15.01.2017, 14:23
	Сообщение было отмечено Nemovok как решение Решение rikimaru2013, в этой задаче достаточно хранить 8 элементов ,мне в егэ такая попадалась когда-то ,если хранить больше ,то балл урежут. 0

@rikimaru2013 2549 / 1208 / 358 Регистрация: 30.11.2013 Сообщений: 3,826
	15.01.2017, 14:32
	Dimension, я всего лишь про магическое число. Думаю самое время загуглить это понятия и понять что я пытаюсь вам донести. Как думаете? 0