Сформировать бригады с минимальным "числом неудобства"

Пожалуйста, помогите решить, я сам пытался, но ничего не получается. Буду очень очень благодарен С:

В классе учатся N человек. Руководитель получил указание направить на субботник R бригад по С человек в каждой.
Все бригады будут заниматься переноской бревен. Каждое бревно одновременно несут все члены одной бригады. При этом бревно нести тем удобнее, чем менее различается рост членов этой бригады.
Числом неудобства бригады будем называть разность между ростом самого высокого и ростом самого низкого членов этой бригады (если в бригаде только один человек, то эта разница равна 0). Руководитель решил сформировать бригады так, чтобы максимальное из чисел неудобства сформированных бригад было минимально.

Формат входных данных:
Сначала вводятся натуральные числа N, R и C — количество человек в классе, количество бригад и количество человек в каждой бригаде (1 ≤ R∙C ≤ N ≤ 100 000). Далее вводятся N целых чисел — рост каждого из N учеников. Рост — натуральное число, не превышающее 1 000 000 000.

Формат выходных данных:
Выведите одно число – наименьшее возможное значение максимального числа неудобства сформированных бригад.

0

Могу предложить без программы поток сознания.
Пусть
Kw:=R*C - количество задействованных в работе учеников
Ki:=N-Kw - количество незанятых в работе учеников
G[1..N] - уже отсортированный список роста учеников.
F[1..N-C+1] - список чисел неудобства бригады из C человек, где F[i] - число неудобства бригады, в которую включены ученики с i по i+C-1.
B[1..C] - состав бригад, где B[i] содержит номер ученика, с которого начинается бригада. Можно хранить в B[i] не просто номер ученика, а только некое смещение, ведь очевидно, что в i-тую бригаду могут включатся ученики от C*(i-1)+1 по C*(i-1)+1+Ki. Таким образом в B[i] находится число от 0 до Ki, причём B[i]<=B[i+1].

Осталось выполнить перебор возможных значений B, и выбрать тот вариант, для которого целевая функция минимальна.
Количество вариантов может быть велико


Поэтому есть смысл применить динамическое программирование.

Может быть, как вариант:
Найти Ki максимальных элементов в F[], пометить индексы, как не подходящие к использованию. Из оставшихся индексов сформировать единственно возможный вариант бригад, подсчитать целевую функцию. Всё.

1

А можно код пожалуйста, а то я не понимаю особо ничего и код попроще, чтоб я в нем разобрался. буду очень очень очень вам благодарен, заранее спасибо за ответ:3

0

На код у меня уже не хватает времени. Но оцениваю его не более, чем 100 строк.
1. Ввод N и массива роста G.
2. Сортировка массива G (любым способом).
3. Расчёт Kw и Ki (от слов work и idle).
4. Расчёт F[i].
5. В цикле поиск наибольших F[i] в количестве Ki штук, запоминание индексов в массиве BadIndexes[1..Ki].
6. Построение однозначного списка бригад (без индексов из BadIndexes). Вычисление максимального из F[i], где i принимает лишь значения начала каждой бригады.
7. Вывод результата.



Добавлено через 23 часа 37 минут
Вот ссылка на разбор задачи.

1