| Цитата(tennisru @ 3.12.2011, 23:19) |
Известно, что чем тяжелее доска, тем она больше может выдержать: если M i>M j, то Si > Sj. сначала надо применить быструю сортировку для M так ? если использовать жадные алгоритм то тогда приграмма будет долго вроде работать или применять его? |
Сортировать можно что по M, что по S - в силу указанного условия это все равно.
Жадный алгоритм как раз быстрее всего, но надо при этом доказать, что он дает оптимальный результат... Похоже, что это именно так в силу монотонности, но вот строгие доказательства никогда не были моей сильной стороной... Что-то в духе - если уж доска не подходит, то положить ее ниже нельзя тем более, а оставить на месте, убрав что-то сверху - ничего не меняет. Нет, что-то не уверен... тут я не специалист. Но перед тем как писать, я тут набросал программку, которая сравнивает жадный и исчерпывающий алгоритмы - по крайней мере несколько тысяч случайно сгенерированных наборов дают основание надеяться, что жадный алгоритм оптимален
