|
|
|
|
|
|
|
Вернуться
| 1 Меньшиков Фёдор Владимирович, 17 августа 2022 г. 18:39:47 | |
|
Сортировка на самом деле не нужна для варианта с 2х. Нужно найти только самый большой камень, все остальные можно применять в любом порядке. Правда интуитивно кажется, что если добавлять камни от больших к маленьким, то разница размеров куч будет поменьше в силу того, что разница никогда не больше веса последнего камня, при котором вес одной кучи обогнал вес другой. Если веса убывают, то НАВЕРНО если последний обгон будет не на третьем камне, а дальше, то и разница будет меньше. Но я не уверен, что тут всё строго и всегда выгодно. Возможно просто sort вызвать проще, чем искать максимум и переставлять в начало.
|
|
|
| 2 Андрей, 17 августа 2022 г. 15:51:03 | |
Спасибо огромное, объяснение - блеск :)
Ещё меня сбивало с толку использование сортировки в реализации на форумах.
|
|
|
| 3 Меньшиков Фёдор Владимирович, 17 августа 2022 г. 15:06:32 | |
|
"ясно" на самом деле расшифровывается так. Есть у нас две кучи, и мы кладём очередной камень в кучу с меньшей суммой. Тогда эта куча или осталась с меньшей суммой, или стала больше. Но она стала больше только за счёт последнего добавленного камня, без него она меньше или равна. Поэтому получается, что после добавления камня она не может быть очень сильно больше. Максимум насколько она больше - вес последнего добавленного камня. И это выполняется всегда. Разность суммарных размеров куч не больше веса последнего добавленного камня. А дальше: размер каждой кучи больше размера самого большого камня. Разница размеров не больше третьего в порядке убывания размеров камня, что не больше того же самого большого камня. Вот отсюда и следует, что разница не более чем в 2 раза.
|
|
|
| 4 Андрей, 17 августа 2022 г. 13:55:26 | |
Случай 1 понятен:
A_SortedDesc[1]> 2*Sum(A_SortedDesc[2..N])
- добавлять во вторую кучу больше нечего, а другое расположение A_SortedDesc[1] (любой конфигурации, где он не один в куче) только "усилит" неравенство
(I)
Непонятно предложение:
"В первую кучу попали и другие камни. Тогда ясно, что веса куч отличаются не более чем на вес самого тяжелого камня, кроме первого. Следовательно и в этом случае условие задачи выполняется."
* Что такое "самый тяжелый камень, кроме первого"? Второй по тяжести из всех A[1..n], т.е. sort()[2]?
* Почему |W1 - W2| <= вес "самого тяжелого камня, кроме первого"?
* Почему из предыдущего условия следует -"Следовательно и в этом случае условие задачи выполняется"
(II)
Как вообще можно придти к этой стратегии?
|
|
|
| 5 Меньшиков Фёдор Владимирович, 17 августа 2022 г. 13:13:11 | |
|
Какая часть доказательства Вам непонятна. Если первый (самый тяжёлый) камень в первой кучке, а все остальные во второй и их суммарный вес меньше половины веса первого камня - тут понятно, что решения не существует? Или не очень понятно, почему?
|
|
|
| 6 Андрей, 17 августа 2022 г. 9:00:35 | |
|
Кстати задача похожа на задачу 71, но с более слабым условием разбиения.
|
|
|
| 7 Андрей, 17 августа 2022 г. 8:58:24 | |
Добрый день! Может быть кто-нибудь поможет, наведет на мысли?
Эти задачи с объяснения видел на нескольких сайтах (например, http://algolist.ru/olimp/sor_prb.php) На форумах приведена куча реализаций этих решений.
Но я не понимаю объяснение. Можно ли эти решения как-то более строго и вместе с тем наглядно доказать/показать?
Задачи:
Задача 2.
Имеется N камней веса А1,А2,...,АN.
Необходимо разбить их на две кучи таким образом, чтобы веса куч отличались не более чем в 2 раза. Если этого сделать нельзя, то указать это.
Задача 3.
Условие задачи 2, только веса куч отличаются не более, чем в 1,5 раза.
"Решения":
Решение задачи 2.
Основная стратегия решения заключается в том, что каждый следующий камень кладется в кучу с меньшим текущим весом. При этом в первую кучу надо положить камень максимального веса. Покажем, что этого достаточно, чтобы гарантировать правильное решение задачи. По окончании распределения камней по кучам возможны 2 ситуации:
1. Все камни попали во вторую кучу, а ее вес остался меньше половины веса первой кучи. Понятно, что в этом случае камни требуемым образом разбить нельзя, следовательно решения не существует.
2. Случай 1. не верен. Тогда возможны следующие ситуации.
а) Все камни попали во вторую кучу. В этом случае ясно, что веса куч отличаются не более чем на половину первой кучи, если вес первой кучи больше, или не более чем вес последнего камня, положенного во вторую кучу. В любом из этих случаев требуемое условие выполняется.
б) В первую кучу попали и другие камни. Тогда ясно, что веса куч отличаются не более чем на вес самого тяжелого камня, кроме первого. Следовательно и в этом случае условие задачи выполняется.
Решение задачи 3.
На начальном этапе в первую кучу кладется самый тяжелый камень, а во вторую - два следующих по весу камня. Для оставшихся камней реализуется описанная для задачи 2 стратегия.
|
|
|
Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!
| | | |
