Скажем, что группа с большей суммой - первая. Пусть Р1 - количество четных чисел в первой группе, Р2 - во второй.
Рассмотрим одну пару отдельно. Если оба элемента одной четности, то на Р1-Р2 это не повлияет(либо Р1+1 и Р2+1, либо Р1+0 и Р2+0). В таких парах будем максимальный элемент добавлять в первую группу.
Теперь остались пары, в которых один элемент Ч, второй НЧ.Пусть их количество Т. Если Т четное, то минимальное Р1-Р2, которое можно получить это 0, иначе - 1. Снова посмотрим на пару в отдельности: у нее либо четный элемент больше, либо нечетный. Хочется всегда в первую группу брать больший, поэтому пока так и сделаем. Но теперь разность Р1 и Р2 не минимальна
Сначала более простой случай, когда Т четное. Пусть К1 пар, у которых четный больше, К2 - у которых нечетный. Допустим, что К1 > К2(обратный случай решается аналогично). Теперь нужно в К1-(Т/2) парах вместо четного взять нечетный. Если мы делаем это в паре [x,y], то сумма первой группы уменьшается на x-y. Мы стремимся, чтобы сумма осталась как можно больше => уменьшилась как можно меньше, поэтому в качестве искомых К1-(Т/2) пар возмем те, у которых разность минимальна.
Случай с нечетным Т усложняется тем, что пар, в которых мы возьмем в первую группу четный элемент, может быть Т/2 и Т/2+1. Просто рассмотрим оба этих случая и выберем наилучший.