Решение задачи Лестница своими руками с Codeforces
Без пояснения   Просмотров: 91
Назовем k-ступенчатой лестницей следующую конструкцию: ровно k+2 деревянные доски, среди которых
две доски длиной хотя бы k+1 — основные направляющие лестницы;
k досок длиной хотя бы 1 — ступеньки лестницы.
Заметим, что ни направляющие, ни ступени не обязаны быть равны.
Например, лестницы 1 и 3 — корректные 2-ступенчатые лестницы, а лестница 2 — корректная 1-ступенчатая. На первом изображении длины досок равны [3,3] для направляющих и [1] для ступеньки. На втором изображении длины досок равны [3,3] для направляющих и [2] для ступеньки. На третьем изображении длины досок равны [3,4] для направляющих и [2,3] для ступенек.
У вас есть n досок. Длина i-й доски равна ai. У вас нет пилы и вы не можете распиливать доски. Зато есть молоток и гвозди, и вы можете собрать импровизированную «лестницу» из тех досок, что есть.
Вопрос в следующем: чему равно максимальное k такое, что вы сможете собрать k-ступенчатую лестницу, используя некоторый поднабор из имеющихся досок?
две доски длиной хотя бы k+1 — основные направляющие лестницы;
k досок длиной хотя бы 1 — ступеньки лестницы.
Заметим, что ни направляющие, ни ступени не обязаны быть равны.
Например, лестницы 1 и 3 — корректные 2-ступенчатые лестницы, а лестница 2 — корректная 1-ступенчатая. На первом изображении длины досок равны [3,3] для направляющих и [1] для ступеньки. На втором изображении длины досок равны [3,3] для направляющих и [2] для ступеньки. На третьем изображении длины досок равны [3,4] для направляющих и [2,3] для ступенек.
У вас есть n досок. Длина i-й доски равна ai. У вас нет пилы и вы не можете распиливать доски. Зато есть молоток и гвозди, и вы можете собрать импровизированную «лестницу» из тех досок, что есть.
Вопрос в следующем: чему равно максимальное k такое, что вы сможете собрать k-ступенчатую лестницу, используя некоторый поднабор из имеющихся досок?