Коррупция

Задача

С целью борьбы с теневой экономикой банк решил внедрить объединение N счетов фирмы в один. За одну операцию объединяются 2 счета и банк автоматически перечисляет на свой счет Р% от суммы объединения за выполнение операции и закрытие одного из счетов. Какая наибольшая сумма может остаться на счету фирмы?

Решение

Скачать код

Разберем код по шагам:

1. Ввод данных:

Запрашивается ввести количество счетов N, процент отчислений P, и суммы денег на каждом из N счетов, которые сохраняются в векторе balances.

2. Создание приоритетной очереди:

Создается минимальная куча (min-heap) pq в нашем случае priority_queue<double, vector<double>, greater<double>>.

Минимальная куча гарантирует, что наименьший элемент всегда находится на вершине.

Все начальные суммы счетов из вектора balances помещаются в приоритетную очередь pq.

3. Цикл объединения счетов:

Цикл while (pq.size() > 1) выполняется до тех пор, пока в очереди не останется только один элемент (один счет).

Внутри цикла:

• Извлекаются два минимальных счета из очереди с помощью pq.top() и pq.pop(). Значения сохраняются в переменных first и second.
• Вычисляется сумма объединения счетов: total = first + second;.
• Вычисляется сумма после вычета комиссии: final_amount = total * (1 - P / 100.0);

Важно разделить P на 100.0, чтобы получить десятичную дробь для расчета процента.

• Полученная сумма final_amount помещается обратно в приоритетную очередь pq.

4. Вывод результата:

После завершения цикла в приоритетной очереди остается только один элемент — итоговая сумма на объединенном счете. Окончательное значение выводится на экран с использованием std::fixed и std::setprecision(2) для форматирования вывода с двумя знаками после запятой.

Ключевые идеи:

Использование минимальной кучи критически важно для эффективности алгоритма. Она позволяет за O(log N) времени извлекать два минимальных элемента. Таким образом, общая сложность алгоритма будет O(N log N), где N — количество счетов.

Данный подход является примером жадного алгоритма. На каждом шаге выбираются два минимальных счета для объединения, что локально дает максимальную сумму перед вычетом комиссии. Доказывается, что такой подход приводит к глобально оптимальному решению — максимизации итоговой суммы.

Формула расчета комиссии: final_amount = total * (1 - P / 100.0);

std::fixed и std::setprecision(2) используются для вывода числа с фиксированной точкой и двумя знаками после запятой, что важно для представления денежных сумм.

system("chcp 1251>nul"); используется для корректного отображения русского текста в консоли Windows.

Пример:

Пусть N = 3, P = 5, и суммы на счетах: 10, 20, 30.

1. Куча: {10, 20, 30}
2. Объединяем 10 и 20: total = 30, final_amount = 30 * (1 - 0.05) = 28.5. Куча: {28.5, 30}
3. Объединяем 28.5 и 30: total = 58.5, final_amount = 58.5 * (1 - 0.05) = 55.575 ≈ 55.58.

Результат: 55.58

Телеграмм канал