C/C++

Жадный алгоритм на Си

Выполняю игру на Codingame - https://www.codingame.com/ide/puzzle/the-gift

Вроде код сделал ( не ругайтесь, что плохой. Еще не форматировал его, внимание уделил только алгоритму) Так вот, после ввода, допустим 3,10,5,6,7. Компилятор засыпает и ничего не выдает. Я пробовал отслеживать выполнение кода, но похоже он даже в циклы не залезает.
Прошу помочь найти ошибку в моем коде ( то есть не писать свой)


Код - https://codeshare.io/bvpkb6 Постарался подробно прокомментировать, если будут вопросы, напишите, пожалуйста
Самая бросающаяся в глаза твоя ошибка: 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]
Евгений Лесовых
Евгений Лесовых
59 174
Лучший ответ
Виталик Павлюк 1)С / (N - i), но у нас ведь должны быть целочисленные значения?
2) ведь в описании greedy algorithm и написано "the optimal solution is the one for which the highest contribution is minimal", то есть у кого больше денег, тот должен внести наибольший относительно других вклад, но в то же время наименьший возможный для себя. Может я перевел неправильно?
Виталик Павлюк что-то я не понял, а почему С / (N - i) вот это действие округляет число? а когда пробую printf("%f", С / (N - i)) то возвращает ноль? Также автор видимо предполагает немного другой алгоритм, для 3,10,5,6,7 и 3,100, 40, 40, 40 работает хорошо, а вот для 3, 100, 1,60,100 не совсем
#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"; //если всю сумму собрали - выводим у кого сколько взяли, иначе ругаемся.
}

На си++ но смысл думаю ясен.
Сергей Чабан
Сергей Чабан
51 416
Евгений Лесовых Для 3 участников поиск сработает. А для прописанных в задаче 2000 участников? Суммарно порядка 4 миллионов итераций внутри min_element - сортировка эффективнее.
А в остальном наши решения не отличаются.