Будем решать данную задачу с помощью перебора. Давайте зафиксируем, сколько раз проводник будет освобождать вагон целиком. Пусть это число равно i. В таком случае, нужно освободить i вагонов так, чтобы максимальное количество людей в одном из оставшихся вагонов было минимально (пусть это количество равно x). Тога проводнику потребуется ровно x выпускать по одному пассажиру из вагонов, где еще остались люди. Следовательно, нужно минимизировать сумму x + i. Поступим следующим образом — отсортируем вагоны по количеству людей в них в невозрастающем порядке. Тогда, зафиксировав какое-то i мы будем целиком освобождать первые i вагонов, а x будет равно ai + 1 или 0, если i было равно n. Итого, взяв минимум по всем i от 0 до n среди значений i + ai + 1 мы получим оптимальный ответ.