Розбір задачі про корупцію

розбір підготовив Dmutro25

Для того, щоб максимізувати суму на рахунку після всіх операцій, ми маємо кожного разу об’єднувати два найменші рахунки. Це дозволяє зменшити втрати від комісії на кожному етапі, оскільки об'єднання великих рахунків не призведе до значних втрат.

Приклад 1

Вхідні дані:

5 10

10 20 30 40 50

Пояснення:

1. Маємо 5 рахунків: 10, 20, 30, 40, 50, і відрахування складають 10%.

2. Спочатку об’єднуємо найменші два рахунки: 10 + 20 = 30, віднімаємо 10%: 30 - (30 * 0.1) = 27.

3. Тепер у нас є рахунки: 27, 30, 40, 50.

4. Об’єднуємо 27 і 30: 27 + 30 = 57, віднімаємо 10%: 57 - (57 * 0.1) = 51.3.

5. Тепер у нас є рахунки: 51.3, 40, 50.

6. Об’єднуємо 40 і 50: 40 + 50 = 90, віднімаємо 10%: 90 - (90 * 0.1) = 81.

7. Тепер у нас є рахунки: 51.3, 81.

8. Об’єднуємо 51.3 і 81: 51.3 + 81 = 132.3, віднімаємо 10%: 132.3 - (132.3 * 0.1) = 119.07.

Приклад 2

Вхідні дані:

3 5 

100 200 300

Пояснення:

1. Маємо 3 рахунки: 100, 200, 300, і відрахування складають 5%.

2. Об’єднуємо 100 і 200: 100 + 200 = 300, віднімаємо 5%: 300 - (300 * 0.05) = 285.

3. Тепер у нас є рахунки: 285, 300.

4. Об’єднуємо 285 і 300: 285 + 300 = 585, віднімаємо 5%: 585 - (585 * 0.05) = 555.75.

Алгоритм

1. Ініціалізуємо структуру даних, яка дозволяє отримувати два найменші рахунки для об’єднання. Для цього використовуємо чергу з пріоритетами (або heap).

2. Вибираємо два найменші рахунки для об'єднання, обчислюємо нову суму після відрахування комісії.

3. Повертаємо результат до черги і повторюємо процес, поки не залишиться один рахунок.

4. Виводимо результат.

Метод heap

Метод heap (черга з пріоритетами) є спеціальною структурою даних, яка дозволяє швидко отримувати мінімальний (або максимальний) елемент. У нашому випадку ми використовуємо min-heap, оскільки нам потрібно на кожному кроці вибирати два найменші елементи для об'єднання.

У мові C++ для реалізації min-heap використовуємо стандартну бібліотеку priority_queue. За допомогою цієї структури можна за O(log n) часу отримати мінімальний елемент, видалити його і додати новий елемент.

Алгоритм по кроках

1. Ініціалізація: Спочатку ми зчитуємо кількість рахунків і процент комісії. Потім додаємо всі суми рахунків у чергу з пріоритетами.

2. Цикл об'єднання: Поки в черзі є більше двох елементів, ми вибираємо два найменші елементи (це гарантується min-heap). Від їх суми віднімаємо комісію і додаємо новий рахунок назад у чергу.

3. Фінальний етап: Коли в черзі залишаються тільки два рахунки, ми об'єднуємо їх остаточно і виводимо результат.

Реалізація на C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, x;
    double p;
    cin >> n >> p;
    priority_queue<double, vector<double>, greater<double>> a;
    
    for(int i = 0; i < n; i++) {
        cin >> x;
        a.push(x); // додаємо рахунки в чергу
    }

    double b;
    p /= 100; // перетворюємо відсотки на десятковий вигляд
    double a1, a2;
    
    while(n != 2) { // поки в черзі більше ніж два рахунки
        a1 = a.top(); // отримуємо мінімальний елемент
        a.pop(); // видаляємо його
        a2 = a.top(); // отримуємо наступний мінімальний елемент
        a.pop(); // видаляємо його

        // об’єднуємо рахунки, враховуючи відсоток комісії
        b = (a1 + a2) - (a1 + a2) * p;
        a.push(b); // додаємо новий рахунок назад у чергу
        n--;
    }
    
    a1 = a.top(); // отримуємо останній рахунок
    a.pop();
    a2 = a.top();
    a.pop();
    b = (a1 + a2) - (a1 + a2) * p; // остаточне об'єднання рахунків

    cout << fixed << setprecision(2) << b; // виводимо результат з точністю до двох знаків
}