Коррупция, задача на жадный алгоритм

309

26 марта 2017, 05:54

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

Коррупция

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

Входные данные:

В первой строке 2 числа: количество счетов N и процент отчислений P.
Во второй строке N чисел: сумма на каждом из счетов фирмы.

Выходные данные:

Наибольшая сумма, которая может остаться на счету.

2 ≤ N ≤ 100000
0 ≤ Р ≤ 20
0 ≤ G ≤ 10000

Входные данные #1:

4 5
1000 1100 1200 1300

Выходные данные #1:

4151.50

Answer 1

Вот как получается ответ.
Думаю, алгоритм отсюда тоже понятен.

// 1000 1100 1200 1300 
console.log((1000 + 1100) * .95) 
// 1200 1300 1995 
console.log((1200 + 1300) * .95) 
// 1995 2375 
console.log((1995 + 2375) * .95) 
// 4151.5

Answer 2

Полное решение задачи будет содержать кучу или иную аналогичную по функционалу структуру (мульти-сет например).

1 - сливать нужно всегда 2 счёта с минимальным кол-вом денег (строго не доказываю).

2 - найти эти 2 счёта можно выталкиванием из кучи.

3 - затолкать что осталось (за вычетом сбора) обратно в кучу.

P.S. G дано в условии, чтобы не боялись переполнения 32-битного типа.