Найдите наибольшую сумму денег, которую владелец магазина может заработать за определенное количество продаж

сортировка списка целых чисел 10^5 — дело миллисекунды. Если ограничение составляет «4 секунды», это фактически бесплатная операция. Чаще всего при решении подобных задач вас действительно беспокоит то, что называется алгоритмической сложностью; обычно обозначается буквой «большое О». Сортировка — это O(n * log n) {n = size of input}, и, как правило, поворотный момент — это O(n^2) — все, что медленнее этого, обычно «слишком медленно», а все, что быстрее, обычно «достаточно быстро», и на кону что-нибудь… путаница. Это все… вещи, для полного освоения которых требуется 5 лет обучения в университете, а Stack Overflow — не лучшее место для публикации книги на 1000 страниц, поэтому обобщений будет достаточно.

Когда у нас есть отсортированный список, этот алгоритм действительно становится очень простым. В конце концов, вы хотите продать тот предмет, которого у вас больше всего, и он находится в начале списка.

Нам необходимо принять во внимание, что продажа этого предмета не приводит к полному исчезновению его запасов; он просто вычитает 1. Самый «быстрый» способ позаботиться об этом — осознать, что если продолжать продавать товар, который начинается с самого высокого запаса, неправильно, алгоритм это легко исправить.

Представьте, что у вас есть входные данные 10,8,8,7. Вы продаете 10, продаете 9, которые становятся, вы продаете 8, которые становятся - пока все хорошо. Но не стоит продавать семерку, которой она стала. Понять это очень легко: вам нужно только посмотреть на следующий товар в магазине, и вам нужно только вспомнить, что у вас в магазине останется n-ное количество семерок, как только у вас закончатся восьмерки.

Однако это немного кодирования, и есть простой выход, который, вероятно, приемлем: просто удалите номер из хранилища и добавьте его обратно. Удаление одного элемента из TreeSet — это O(log n); так же добавляет. Мы собираемся добавлять/удалять m предметы, где m — это «вы можете продать ЭТО много предметов», которое также ограничено 10^5, что является довольно небольшим числом, так что это O(m * log n). Предполагая, что n и m имеют одинаковую общую величину (все это не более 10^5, как вы это объяснили), тогда O(n*log n) отсортируем его и O(n*log n) запустим алгоритм; постоянные факторы не учитываются, так что это O(n * log n + n * log n), то есть O(2 * n * log n), что есть... просто еще раз O(n log n): алгоритм стал медленнее только из-за постоянного фактора, который не имеет значения (чтобы сделать это реалистичным: потому что вы можете просто бросить несколько центов в IAAS поставщик более быстрого процессора, который будет опережать постоянный коэффициент. Вы не можете сделать это для алгоритма, который, например, O(n^3) (при добавлении большего количества входных данных для решения проблемы время, необходимое для ее решения, будет выглядеть как кривая y = x^3 с включенным «размером входных данных»). ось X и «затраченное время» на Y, и если вы посмотрите на y = x^3, это очень крутая линия — деньги не могут бороться с этой линией. Они могут бороться с y = x или, в данном случае, y = 1.

Собрать это вместе предельно тривиально:

List<Integer> itemsAvailable = readThisFromTheInput();
int sales = readThisAsWell();

var items = new TreeSet<Integer>(itemsAvailable);
long answer = 0;
for (int i = 0; i < sales; i++) {
  int v = items.pollLast();
  answer += v;
  items.add(v - 1);
}

System.out.println(answer);

(TreeSet сохраняет свое содержимое отсортированным по своей сути.)

Вот решение с использованием TreeMap. Это работает следующим образом.

• вычислить частоту всех элементов.
• затем возьмите последний предмет (самый дорогой) с карты.
• добавляй в revenue.
• измените частоту появления этого товара на 1, чтобы уменьшить количество доступных товаров по этой цене.
• если (это 1, удалите его) с карты.
• теперь увеличьте частоту item-1 или создайте новую запись, если она не существует.
• продолжать до тех пор, пока m == 0

Включена дополнительная логика, которая генерирует исключение, если запасы превышают желаемые продажи. Можно также просто вернуть то, что было вычислено с доступными элементами. Это зависит от того, что требуется.

public static long getMaximumAmount(List<Integer> arr, int m) {
    TreeMap<Integer, Integer> inventory = arr.stream()
            .collect(Collectors.toMap(a -> a, b -> 1, Integer::sum,
                    () -> new TreeMap<>()));
    long revenue = 0;
    while (m > 0) {
        if (inventory.isEmpty()) {
                  throw new RuntimeException("Insufficient items to meet sales");
        }
        Entry<Integer,Integer> e = inventory.lastEntry();
       
        int item = e.getKey();
        int remaining =e.getValue();
        revenue += item;
        if (e.getValue() == 1) {    // remove it as
            inventory.remove(item); // no more remaining
        } else {
            inventory.put(item, remaining-1); // update
        }
        // create new entry or increment existing
        // don't update if item will be <= 0
        if (item > 1) {
           inventory.compute(item-1, (k,v)->v == null ? 1 : v+1);
        }
        m--;
    }
    return revenue;
}

Похоже, это работает для широкого диапазона значений и продаж менее чем за секунду.