• Минимизация фактов выплат/перевозок?

    @apodavalov Автор вопроса
    Добрый день!


    Извиняюсь, что долго не отвечал. Слег с болезнью под новый год. Потом что-то руки не доходили. Сейчас дошли.

    Во-первых, спасибо большое!

    Во-вторых, портировал на C#. Я напишу тут несколько замечаний, чтобы исправить ошибки, которые (возможно) есть в коде.

    equalizer.cpp


    Строка 268:

    for (int i = 0; i < sorted_balance.length() — 1; i++)

    Почему "- 1"?

    Строка 87:

    Строка 239:

    if (temp.isEmpty() || temp_list.length() + 1 < temp.length())

    Почему "+ 1"?

    Строка 119:

    Вот это:

    if (!used.contains(first_key))

    {

    for (int j = i + 1; j < balance.keys().length(); j++)

    Нужно сделать так:

    for (int j = i + 1; j < balance.keys().length() && !used.contains(first_key); j++)

    Так как first_key может попасть в массив used внутри цикла по j


    В третьих, по поводу кода: пока среди моих тестов проходят все. Подготовлю тесты побольше. И буду вкуривать теперь логику работы. Еще раз спасибо =)

    Добавлено спустя два года:
    Для того, чтобы решить задачу достаточно найти все минимальные подгруппы в которых сумма балансов равна 0 (в таких группах не содержатся другие подгруппы сумма балансов которых равна 0). Затем просто раздать балансы внутри полученных подгрупп "в лоб".
    Для решения первой подзадачи можно использовать: https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D...
    Ответ написан
    Комментировать