Найти пару чисел с минимальной суммой и разницей между ними не меньше 4

@VWVVWV · Регистрация: 30.12.2016

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

Привет, народ. Сегодня запоролся на одной задаче из ЕГЭ. Суть такая: нам вводится количество чисел и сами числа. Нам нужно найти пару чисел, чтобы их сумма была минимальной и расстояние между ними было не меньше 4. Программа не должна перебирать все пары чисел. Буду бесконечно благодарен, если опишите решение словами, а не кодом. Заранее спасибо всем, кто помог.

@outoftime · 18.02.2018, 21:15

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

Суть такая

Такое ощущение, будто тот кто не решил задачу знает какая у нее суть.

В целом, не мешало бы добавить конкретики, а лучше условие задачи слово в слово.

Добавлено через 1 час 0 минут
VWVVWV, как вариант можно задачу переформулировать так: есть точка которая разбивает наши числа на две части слева расстоянием больше 4 и, также, справа. Нужно из этих 2х отрезков найти минимальное, что есть ничто иное как поиск минимум на отрезке http://e-maxx.ru/algo/rmq сложность $https://www.cyberforum.ru/cgi-bin/latex.cgi?O(\log{N})$ так как надо надо пройти по всем точкам тогда общая сложность выходит $https://www.cyberforum.ru/cgi-bin/latex.cgi?O(N \log{N})$ что меньше за квадрат.

Добавлено через 1 минуту
Вот еще поиск минимума можно сделать в 2ух массивах начиная с правого и левого концов, тогда на препроцессинг уйдет $https://www.cyberforum.ru/cgi-bin/latex.cgi?O(N)$ и ответ будет за $https://www.cyberforum.ru/cgi-bin/latex.cgi?O(1)$ и в результате получим решение за $https://www.cyberforum.ru/cgi-bin/latex.cgi?O(N)$ вот только памяти потребуется 3 N - исходный массив и 2 массива минимумов с правого и левого концов до данной точки

@VWVVWV · 19.02.2018, 04:04 **[ТС]**

Допустим, массив 4 5 7 2 3 1 6 3 1
По данному алгоритму мы заметим первую пятерку и сложим её с четверкой и получим 5, но выгоднее было бы взять последнюю и сложить её с двойкой.

@outoftime · 19.02.2018, 05:43

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

По данному алгоритму

читай пока не поймешь Найти пару чисел с минимальной суммой и разницей между ними не меньше 4

@zss · 19.02.2018, 07:12

Зачем мудрить

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int m[N];
//......
int x,y;
bool found=false;
for(int i=0;i<N-1;i++)
{
    for(int j=i+1;j<N;j++)
    {
        if(abs(M[i]-M[j)>=4)
        {
            if (!found || x+y>M[i]+M[j])
            {
                x=M[i];
                y=M[j];
                found=true;
            }
       }
   }
}
if(found)
   cout<<x<<' '<<y;

@outoftime · 19.02.2018, 08:35

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

Зачем мудрить

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

не должна перебирать все пары чисел

Т.е. квадрат - не вариант. У меня решение простейшее за линию.

@VWVVWV · 19.02.2018, 19:13 **[ТС]**

Не разницей на 4, а расстоянием между элементами не менее 4.
Вот тебе пример: 1 2 2 2 1 - между единицами расстояние 4, все ок.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .
SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer 8Observer8 08.02.2026 Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .	SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств 8Observer8 07.02.2026 Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .	SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .

@VWVVWV 0 / 0 / 1 Регистрация: 30.12.2016 Сообщений: 9

	Найти пару чисел с минимальной суммой и разницей между ними не меньше 4 18.02.2018, 16:22. Показов 2742. Ответов 6 Метки нет (Все метки) Привет, народ. Сегодня запоролся на одной задаче из ЕГЭ. Суть такая: нам вводится количество чисел и сами числа. Нам нужно найти пару чисел, чтобы их сумма была минимальной и расстояние между ними было не меньше 4. Программа не должна перебирать все пары чисел. Буду бесконечно благодарен, если опишите решение словами, а не кодом. Заранее спасибо всем, кто помог. 0

@VWVVWV 0 / 0 / 1 Регистрация: 30.12.2016 Сообщений: 9
	19.02.2018, 04:04 [ТС]
	Допустим, массив 4 5 7 2 3 1 6 3 1 По данному алгоритму мы заметим первую пятерку и сложим её с четверкой и получим 5, но выгоднее было бы взять последнюю и сложить её с двойкой. 0

@VWVVWV 0 / 0 / 1 Регистрация: 30.12.2016 Сообщений: 9
	19.02.2018, 19:13 [ТС]
	Не разницей на 4, а расстоянием между элементами не менее 4. Вот тебе пример: 1 2 2 2 1 - между единицами расстояние 4, все ок. 0