Меня спросили об этом по рейтингу хакера, и я не нашел решения, которое не исчерпало бы отведенное время. Я использовал php и выделил время было 9 секунд ...

Идея в том, что есть «билетные кассы» с определенным количеством билетов, скажем, 9. Любой билет, который они продают, оценивается по количеству оставшихся билетов, поэтому первый билет будет стоить 9 долларов, второй - 8 долларов и т. Д.

Вам даны две строки данных, скажем:

2 4
1 5

Первая строка содержит два числа:

Количество киосковСколько билетов продано

Вторая строка содержит список того, сколько билетов у каждого киоска изначально, поэтому в этом случае в киоске 1 есть 1 билет, в киоске 2 - 5 билетов.

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

В этом случае вы продаете четыре билета из киоска два по цене 5 + 4 + 3 + 2 = 14 долларов.

Так как ты это решаешь. Я выяснил два пути, оба из которых не хватило времени

Загрузите номера киосков (вторая строка) в массив. Пройдите через этот массив N раз (количество билетов для продажи), выбрав наибольшее число, добавив его в агрегатор и уменьшив это число. Тогда у вас есть сумма в агрегаторе.

Загрузите номера киосков в массив. Сортировать массив. Идите назад через массив и, как вы делаете: сохраните это число (текущее), добавьте его в агрегатор, перейдите к следующему значению. Если он тот же (текущий), то добавьте его в агрегатор, вычтите из него 1 и продолжайте. Если он отличается, вернитесь к концу массива и начните снова. Сделайте это N раз (внутренний цикл, а не внешний).

Проблема: ни один не работал.

Кто-нибудь может придумать лучшее решение?