2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Нахождение максимального количества пар в списке
Сообщение04.11.2018, 12:50 
Заслуженный участник


06/07/11
5627
кран.набрать.грамота
arseniiv в сообщении #1351589 писал(а):
Угу. Если вы намекаете на кое-что, что мы тут не будем упоминать явно, чтобы не заспойлить решение целиком, то раз здесь нужно лишь посчитать число удовлетворяющих пар, а не перебирать их, квадратичность превращается в линейность.
Нет, я намекал на то, что время будет не линейное.
И я как-то не очень представляю, как посчитать количество пар, не перебирая их.

 Профиль  
                  
 
 Re: Нахождение максимального количества пар в списке
Сообщение04.11.2018, 12:56 
Заслуженный участник


27/04/09
28128
Написал ЛС, перепроверьте идею. :-)

 Профиль  
                  
 
 Re: Нахождение максимального количества пар в списке
Сообщение04.11.2018, 13:22 


27/08/16
9426
Самое главное не учесть одну ти ту же пару несколько раз. В общем, проход по списку двумя индексами (в Питоне список это массив), для каждого элемента $a$ во внешнем цикле находим граничный элемент $b$ (максимальный, такой, что $b \le 2 a$) во внутреннем цикле и прибавляем его номер (индекс плюс 1) к счётчику. Индекс $b$ сохраняем между внутренними итерациями. Правильную обработку отрицательных чисел и повторов оставляю ТС.

 Профиль  
                  
 
 Re: Нахождение максимального количества пар в списке
Сообщение04.11.2018, 20:56 


14/09/18
15
Всех благодарю за ответы! Постараюсь на днях разобраться и самостоятельно решить.

 Профиль  
                  
 
 Re: Нахождение максимального количества пар в списке
Сообщение06.11.2018, 17:25 


14/09/18
15
Pphantom в сообщении #1351591 писал(а):
Остался, пожалуй, только один вопрос, ответ на который влияет на реализацию: под словом "список" в исходном условии понимался именно соответствующий тип данных или массив тоже сойдет?

Извиняюсь, не заметил вопрос. Да, имеется ввиду тип данных.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 20 ]  На страницу Пред.  1, 2

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group