Найти разбиение старушек на группы, разговорчивость которых минимальна - C#
Формулировка задачи:
В этом году Иван Иванович решил отметить приход осени субботником, чтобы убрать весь мусор во дворе дома номер 31 по улице Осенней. На субботник он пригласил N знакомых старушек, живущих в том же самом доме. Однако, в самом начале мероприятия выяснилось, что по одиночке старушки работают плохо, так как им хочется во время работы еще и поговорить друг с другом.
Иван Иванович подумал и принял волевое решение разбить старушек на группы так, чтобы в каждой группе было не менее 2 старушек. Старушки отличаются друг от друга уровнем разговорчивости, и если в одну группу попадут две старушки, у одной из которых маленький уровень разговорчивости, а у второй - большой, то они не могут поговорить друг с другом и работа будет стопориться.
Назовем разговорчивостью группы разность между максимальным и минимальным уровнями разговорчивости старушек в группе. Например, если уровни разговорчивости старушек в группе равны 7, 3 и 11, то разговорчивость группы равна 11 - 3 = 8. Разговорчивостью разбиения старушек на группы назовем максимальную из разговорчивостей групп, входящих в разбиение.
Требуется написать программу, которая поможет Ивану Ивановичу найти разбиение старушек на группы, разговорчивость которого минимальна.
Решение задачи: «Найти разбиение старушек на группы, разговорчивость которых минимальна»
textual
Листинг программы
using System;
class Program
{
static void Main()
{
int N = 10;
int[] volubility = new int[N];
Random r = new Random();
for (int n = 0; n < N; n++)
Console.Write((volubility[n] = r.Next(0, 20)) + " ");
Array.Sort(volubility);
int serial = 1, maxGroupVol = 0, i = N - 2;
while (true)
{
int curmin = 0, curmax = volubility[i + 1];
bool minFound = false;
Console.Write("\nGroup #{0}: {1} ", serial, curmax);
for (; i > 0; i--)
{
if (volubility[i] == curmax)
Console.Write(curmax + " ");
else if (!minFound)
{
curmin = volubility[i];
minFound = true;
Console.Write(curmin + " ");
}
else if (volubility[i] != curmin)
{
serial++;
break;
}
else if (volubility[i] == curmin)
Console.Write(volubility[i] + " ");
}
i--;
if (i < 1)
Console.Write(curmin = volubility[0]);
if (maxGroupVol < curmax - curmin)
maxGroupVol = curmax - curmin;
if (i < 1)
break;
}
Console.WriteLine("\nMax volubility: " + maxGroupVol);
Console.ReadKey();
}
}