Жадный алгоритм на Си
Выполняю игру на Codingame - https://www.codingame.com/ide/puzzle/the-gift
Вроде код сделал ( не ругайтесь, что плохой. Еще не форматировал его, внимание уделил только алгоритму) Так вот, после ввода, допустим 3,10,5,6,7. Компилятор засыпает и ничего не выдает. Я пробовал отслеживать выполнение кода, но похоже он даже в циклы не залезает.
Прошу помочь найти ошибку в моем коде ( то есть не писать свой)
Код - https://codeshare.io/bvpkb6 Постарался подробно прокомментировать, если будут вопросы, напишите, пожалуйста
время - 1:23 поправил немного алгоритм
Самая бросающаяся в глаза твоя ошибка: while (1); { - точки с запятой здесь быть не может.
Но смысл задачи в том, чтобы максимально равномерно распределить платежи по ВСЕМ участникам. Жадный алгоритм тут категорически не подходит.
У тебя сам подход ошибочен. Надо начинать не с наибольших, а с наименьших значений и двигаться к наибольшим.
Сортируем block по возрастанию и далее:
Цикл по i от 0 до N - 1 включительно:
block2[i] = min(block[i], С / (N - i))
С -= block2[i]
Конец цикла
Если C больше 0: выводим "IMPOSSIBLE"
Иначе: выводим block2
И это всё. Суммировать block и сравнивать сумму с C не требуется.
Собственно, block2 тоже не нужен - ответ можно сохранять в block:
block[i] = min(block[i], С / (N - i))
С -= block[i]
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
uint16_t budget[]{ 3,100,100 }; //участники
uint16_t* ukazatel;
uint16_t pos{};
uint16_t result[3]{}; //для вывода результата
int size = 3; // сколько участников
int need = 100; //сумма которую нужно собрать
int need_all{};
while (size) // пока число участников дележа !=0
{
need_all = need / size; //вычисляем средний (оптимальный) платеж оставшихся участников
ukazatel = min_element(budget, budget + 3); //находим у кого меньше всего денег (по указателю)
pos = ((size_t)ukazatel - (size_t)budget) / sizeof(uint16_t); //преобразовываем указатель в номер элемента
result[pos] = need_all > *ukazatel ? *ukazatel : need_all; //если денег достаточно - берем оптимальный, иначе - забираем сколько есть
*ukazatel = -1; //вбиваем общипанному участнику максимально возможную сумму чтобы исключить из поиска
need -= result[pos]; //обновляем сумму которую необходимо собрать
--size; //обновляем количество участников
}
if (!need) for (auto& i : result) cout << i << " "; else cout << "Imposible"; //если всю сумму собрали - выводим у кого сколько взяли, иначе ругаемся.
}
На си++ но смысл думаю ясен.