|
18 / 18 / 9
Регистрация: 12.10.2014
Сообщений: 100
|
|
Задача про кубики22.04.2016, 18:35. Показов 2816. Ответов 11
Метки нет (Все метки)
Есть столбики указанных размеров. Задание такое: Какое наименьшое количество перекладываний необходимо сделать, что бы высота 2х любых столбиков не отличалась больше чем на 1. Кроме того, за один раз можно перекладывать только один кубик из любого в столбика в соседний.
Входные данные (в первый элемент - количество столбиков, последующие - их высота): 5 3 4 8 2 5 Выходные данные (одно число - наименьшее количество перекладываний): 4 С чего стоит начать решение это задачи? Мне не сколько код необходим(сам могу написать), сколько алгоритм решения, с чем я прошу вас помочь.
0
|
|
| 22.04.2016, 18:35 | |
|
Ответы с готовыми решениями:
11
|
|
Вездепух
13184 / 6820 / 1821
Регистрация: 18.10.2014
Сообщений: 17,260
|
||
| 22.04.2016, 18:49 | ||
|
Так а "уничтожать" столбики можно или нет? Т.е. если я перемещу все кубики из одного столбика в другой, означает ли это что исходный столбик исчез? Или это означает, что столбик остался, но имеет высоту 0?
0
|
||
|
18 / 18 / 9
Регистрация: 12.10.2014
Сообщений: 100
|
||
| 22.04.2016, 18:54 [ТС] | ||
|
Добавлено через 2 минуты Вот полное условие: На День рождения своего племянника Петрика Степан подарил ему набор кубиков. Петрик тут же стал строить из кубиков забор, однако столбики у Пети выходили разной высоты. Степана заинтересовал вопрос: "Какое наименьшее количество переложений можно сделать, чтобы высота любых двух столбиков отличалась не более чем на один кубик. Кроме того за один раз можно переводить только один кубик из произвольного колонки на рядом расположен. Входные данные В первой строке входного файла записано число N (1 ≤ N ≤ 1000) - количество столбиков с кубиками в Петрика. Вторая строка содержит N целых чисел - высоту каждого столбика (в кубиках). Все числа не превышают 106 . Выходные данные В выходной файл необходимо вывести одно единственное число - наименьшее количество переложений кубиков, в результате которых высота любых двух столбиков не будет отличаться более чем на один кубик. пример: Ввод: 5 3 4 8 2 5 Вывод: 4 Объяснение: Сделать два перекладывание из колонки №3 в столбик №4. результат - 3 4 6 4 5. Затем переложить кубик из колонки №2 в столбик №1. Результат - 4 3 6 4 5 И напоследок переместить кубик из колонки №3 в столбик №2. Результат - 4 4 5 4 5.
0
|
||
|
68 / 68 / 37
Регистрация: 26.10.2013
Сообщений: 198
|
||
| 22.04.2016, 20:59 | ||
|
PaT TEma,
При 3 4 6 4 5 надо переложить с к. №3 в к. №1 - и результат будет тот же 4 4 5 4 5. Ну это так, к слову. Реализация должна быть такой: на каждом ходу перекладывается один кубик из самого высокого столбца на самый низкий пока не будет выполнено условие.
0
|
||
|
Вездепух
13184 / 6820 / 1821
Регистрация: 18.10.2014
Сообщений: 17,260
|
|||
| 22.04.2016, 21:12 | |||
|
Если бы перекладывать разрешалось откуда угодно куда угодно, то задача была бы совсем тривиальной.
1
|
|||
|
68 / 68 / 37
Регистрация: 26.10.2013
Сообщений: 198
|
||
| 22.04.2016, 21:44 | ||
|
Эх, уже сделал код на неправильное условие (.
0
|
||
|
Вездепух
13184 / 6820 / 1821
Регистрация: 18.10.2014
Сообщений: 17,260
|
|
| 22.04.2016, 22:13 | |
|
Понятно, что привести столбики в правильное состояние - это привести все высоты в диапазон
[Hmin, Hmax], где K - общее количество кубиков, Hmin = floor(K/N), Hmax = ceil(K/N).Однако жадная стратегия "берем слишком высокий и сбрасываем в ближайший < Hmax, берем слишком низкий и дополняем из ближайшего > Hmin" не всегда дает оптимальный результат...
0
|
|
|
68 / 68 / 37
Регистрация: 26.10.2013
Сообщений: 198
|
||||||
| 22.04.2016, 23:42 | ||||||
|
PaT TEma, прошу сильно не бить, но единственное, что приходит в голову - перебор через рекурсию.
1
|
||||||
|
techpriest
634 / 213 / 57
Регистрация: 27.02.2014
Сообщений: 1,180
|
|
| 22.04.2016, 23:57 | |
|
Нда... Я за перебор с отсевом заведомо ухудшающих ситуацию вариантов и вариантов, длительность которых больше чем самого быстрого найденного.
0
|
|
|
68 / 68 / 37
Регистрация: 26.10.2013
Сообщений: 198
|
|
| 23.04.2016, 00:12 | |
|
0
|
|
|
18 / 18 / 9
Регистрация: 12.10.2014
Сообщений: 100
|
|
| 23.04.2016, 00:29 [ТС] | |
|
RQdan, всё отлично, осталось оптимизировать. А то сильно долго выполняется. Мне нужно не больше 1сек. Попробую что то сделать
0
|
|
|
techpriest
634 / 213 / 57
Регистрация: 27.02.2014
Сообщений: 1,180
|
||||||
| 23.04.2016, 09:58 | ||||||
|
Вот. У меня теперь быстро.
Можно расскометировать работу с векторами. Станет медленно, но можно будет просмотреть вариант.
Проблемма алгоритма в том, что его скорость зависит от начальной заданной глубины поиска. Добавлено через 7 минут Попробовал увеличивать число допустимых ходов по одному в цикле. Тобишь... Не нашла при такой глубине, ищи глубже. В общем... Ходов так до 10 -мгновенно.... Дальше - комбинаторный взрыв. Добавлено через 5 минут Скорее всего, всё-таки жадность нужна .
1
|
||||||
| 23.04.2016, 09:58 | |
|
Помогаю со студенческими работами здесь
12
Про кубики 3 задачи: про цветные шарики, окрашенные кубики и делители числа. Задача Кубики Задача C. Кубики Ускорить код.Задача кубики Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
Модель ЗдрввоСохранения 7: больше работников, больше ресурсов.
anaschu 08.04.2026
работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20%
kYBz3eJf3jQ
|
Дальние перспективы сервера - слоя сети с космологическим дизайном интефейса карты и логики.
Hrethgir 07.04.2026
Дальнейшее ближайшее планирование вывело к размышлениям над дальними перспективами. И вот тут может быть даже будут нужны оценки специалистов, так как в дальних перспективах всё может очень сильно. . .
|
Горе от ума
kumehtar 07.04.2026
Эта мне ментальная установка, что вот прямо сейчас, мол, мне для полного счастья не хватает (нужное вписать), и когда я этого достигну - тогда и полный кайф. Одна из самых сильных ловушек на пути. . . .
|
Использование значений реквизитов справочника в документе, с определенными условиями и правами
Maks 07.04.2026
1. Контроль срока действия договора
Алгоритм из решения ниже реализован на примере нетипового документа "ЗаявкаНаРаботу", разработанного в конфигурации КА2.
Задача: уведомлять пользователя, если. . .
|
|
Доступность команды формы по условию
Maks 07.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2.
Задача: сделать доступной кнопку (команда формы "ЗавершитьСписание") при. . .
|
Уведомление о неверно выбранном значении справочника
Maks 06.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "НарядПутевка", разработанного в конфигурации КА2.
Задача: уведомлять пользователя, если в документе выбран неверный склад. . .
|
Установка Qt Creator для C и C++: ставим среду, CMake и MinGW без фреймворка Qt
8Observer8 05.04.2026
Среду разработки Qt Creator можно установить без фреймворка Qt. Есть отдельный репозиторий для этой среды: https:/ / github. com/ qt-creator/ qt-creator, где можно скачать установщик, на вкладке Releases:. . .
|
AkelPad-скрипты, структуры, и немного лирики..
testuser2 05.04.2026
Такая программа, как AkelPad существует уже давно, и также давно существуют скрипты под нее. Тем не менее, прога живет, периодически что-то не спеша дополняется, улучшается. Что меня в первую очередь. . .
|