Сразу хочется сказать - пост нацелен на то, чтобы показать людям, которые ругаются, что контест - маздай, автор контеста - бяка, и как вообще можно давать задачи с непонятной оценкой сложности (типа второй), что они не правы, и после непродолжительных размышлений оказывается, что сложность алгоритма - O(n^2*log(максимальное число)), пусть и с бОльшей константой, нежели при простом бинарном поиске. Этим как раз и хороша задача - она проверяет, действительно ли кодер умеет оценивать сложность, или только знает набор стандартных шаблонов.

Пусть C - это разрыв между максимальным и минимальным числами в нашем наборе, числа могут быть любыми. После не более чем n-1 шагов работы жадного алгоритма (взять минимальное число и проделать, что написано в задаче) мы получаем новое значение разрыва C^ < C*(1-1/n). Почему так? Очевидно, что минимальное число придется увеличить на величину не меньше, чем C/n (в худшем случае - когда еще n-2 числа мимимальны, а последнее - на C больше). Остальные числа, если они оказываются меньше нового минимального - увеличиваются как минимум до его же уровня (а на самом деле - больше, поскольку среднее в это время тоже растет, мы же, из консервативности, зафиксировали его на уровне минимального числа + C/n).

Вот и получается, что за не более чем за n-1 шаг жадного алгоритма разрыв (C) сокращается как минимум до C*(1-1/n). А это все, товарищи! Это означает, что количество шагов жадного алгоритма будет порядка O(n*log(С, логарифм по основанию 1+1/(n-1))), а поскольку каждый шаг - это O(n), то общая сложность - O(n^2*log(максимальное число)), as was stated in the beginning of this outline! Правда, работать это будет чуть дольше, чем бинарный поиск - поскольку логарифм по основанию 1+1/n, то есть в худшем случае порядка 1.02, но константа 1/ln(1.02) ~ 1/0.2 ~ 50 совсем некритична.

P.S. То есть, на самом-то деле, при n --> INF любители математики могут получить, что сложность есть O(n^3*log(max)), предполагая обычный двоичный логарифм и обычную константу, но даже в этом случае при заданных ограничениях задача все равно летает.

Старался объяснить настолько понятно, насколько мог. Если нужно что пояснить - пишите.