0

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

Коррупция

С целью борьбы с теневой экономикой банк решил внедрить объединение 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
3
  • можете объяснить как получается ответ в первом тесте ? Всё перепробовал. Commented 23 мар. 2017 в 14:30
  • а лучше если вы покажете как решить эту задачу ,чтобы технику решения задач на жадные алгоритмы посмотреть . Commented 23 мар. 2017 в 14:31
  • 2
    Данный вопрос следует закрыть, потому что это просьба сделать работу за автора (решить задачу с нуля) Commented 23 мар. 2017 в 15:29

2 ответа 2

2

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

// 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

2

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

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

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

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

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

16
  • 1
    32-битного? Там же промежуточные результаты всё равно дробные. Или следует как-то потом считать процент от суммы?
    – Qwertiy
    Commented 23 мар. 2017 в 14:47
  • 1
    Судя по тому, что решение не проходит большинство тестов, там какие-то заморочки с вычислениями - если брать double, а потом округлять до копеек - не работает... Похоже, фокус там именно в этом расчете...
    – Harry
    Commented 23 мар. 2017 в 14:54
  • @Harry, интересно. А точно жадно сливать верно? Не может быть подвоха?
    – Qwertiy
    Commented 23 мар. 2017 в 15:00
  • @Harry а ссылку на задачу можно?
    – pavel
    Commented 23 мар. 2017 в 15:02
  • 1
    e-olymp.com/ru/problems/21
    – Harry
    Commented 23 мар. 2017 в 15:05

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.