дано кол-во досок N, дальше в N строках их характеристики n

 M 1 S 1

 M 2 S 2

 ...

 M n S n
 где слева масса доски , справа вес который она может выдержать (там и там величины в кг)
 нужно вывести максимальное количество досок, из которых можно построить башню в высоту,
 каждая доска лежит сверху предыдущей
 Известно, что чем тяжелее доска, тем она больше может выдержать: 
 если M i>M j, то Si > Sj.

 сначала надо применить быструю сортировку для M так ?
 если использовать жадные алгоритм то тогда приграмма будет долго вроде работать или применять его?
 заранее спасибо

Сортировать можно что по M, что по S - в силу указанного условия это все равно.

Жадный алгоритм как раз быстрее всего, но надо при этом доказать, что он дает оптимальный результат... Похоже, что это именно так в силу монотонности, но вот строгие доказательства никогда не были моей сильной стороной... Что-то в духе - если уж доска не подходит, то положить ее ниже нельзя тем более, а оставить на месте, убрав что-то сверху - ничего не меняет. Нет, что-то не уверен... тут я не специалист. Но перед тем как писать, я тут набросал программку, которая сравнивает жадный и исчерпывающий алгоритмы - по крайней мере несколько тысяч случайно сгенерированных наборов дают основание надеяться, что жадный алгоритм оптимален 



Это сообщение отредактировал(а) disputant - 4.12.2011, 15:32

можете показать исходник?

Отправил в личку.