Коррупция

Задача

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

Решение

#include <iostream>
#include <queue>
#include <vector>
#include <iomanip>
#include <format>

using namespace std;

int main() {
    system("chcp 1251>nul");
    int N;          // Количество счетов
    double P;       // Процент отчислений

    // Сообщения на кириллице для ввода данных
    cout << "Введите количество счетов N: ";
    cin >> N;
    cout << "Введите процент отчислений P: ";
    cin >> P;
    vector<double> balances(N);
    cout << "Введите суммы на счетах:\n";
    for (int i = 0; i < N; ++i) {
        cout << "Счёт № " << i+1<<" ->";
        cin >> balances[i];
    }

    // Минимальная куча для хранения счетов фирмы
    priority_queue<double, vector<double>, greater<double>> pq;

    // Заполняем кучу начальными суммами
    for (double balance : balances) {
        pq.push(balance);
    }

    // Процесс объединения счетов
    while (pq.size() > 1) {
        // Берем два минимальных счета
        double first = pq.top(); pq.pop();
        double second = pq.top(); pq.pop();

        // Сумма объединения счетов
        double total = first + second;
        // Вычитаем процент комиссии P%
        double final_amount = total * (1 - P / 100.0);

        // Возвращаем итоговую сумму обратно в кучу
        pq.push(final_amount);
    }

    // Осталась только одна сумма, выводим ее
    cout << std::fixed << std::setprecision(2)
        << "Наибольшая сумма, которая может остаться на счету: "
        << pq.top() << endl;

    return 0;
}

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

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

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