Доминошка — это прямоугольная плитка, лицевая сторона которой разделена на два квадрата, каждый из которых содержит от 0 до 6 точек. Ряд доминошек выложен на столе:
6 1 1 1
- - - -
1 5 3 2
Количество точек в верхней строке равно 6 + 1 + 1 + 1 = 9 и количество в нижней — 1 + 5 + 3 + 2 = 11. Разница между нижней и верхней строкой равна |11 - 9| = 2. Разница — это абсолютное значение разности двух сумм. Каждая доминошка может быть повернута на 180 градусов, меняя местами верхний и нижний квадраты.
Необходимо определить, какое минимальное количество поворотов необходимо для минимизации разницы.
В приведенном примере нужно повернуть последнюю доминошку для того, чтобы уменьшить разницу до нуля. В этом случае ответом будет 1.
Входной файл in.txt подготовлен следующим образом:
* первая строка содержит целое n (1 ≤ n ≤ 250 000), определяющее количество доминошек, лежащих на столе;
* каждая из следующих n строк содержит два целых числа a и b, разделенных пробелом (0 ≤ a, b ≤ 6); числа a и b, записанные в i+1 строке входного файла определяют количество точек на i-ой доминошке в верхнем и нижнем квадратах соответственно.
Выходной файл out.txt должен содержать одно число, которое равно наименьшему количеству поворотов, необходимых для минимизации разности.
Пример входных данных
4
6 1
1 5
1 3
1 2
Пример выходных данных
1
---------------------------------------------------------------------------------------------------------------------------------------------
Вот моя скромная идея
Пусть (a, b) - доминошка, a - кол-во точек на верхнем квадрате, b - на нижнем. Тогда поворот доминошки увеличивает или уменьшает разницу между верхней и нижней суммами на 2*|a - b|. Тогда каждой доминошке можно поставить в соответствие число:
2*|a - b| - если она уменьшает разницу между суммами.
-2*|a - b| - если увеличивает
Тогда получаем массив четных чисел диапозона от -12 до 12. Например, в приведенном в условии примере:
6 1 1 1
- - - -
1 5 3 2
соответствует: -10, 8, 4, 2
Разница x равна 2.
Значит, задача сводится к тому, как эффективно в массиве четных целых чисел выбрать наименьшее кол-во чисел так, чтобы их сумма была наиболее близка к разнице x. Вот тут мои мысли заканчиваются
Как это эффективно сделать за время O(n) или хотя бы O(n*log(n)) операций? Помогите идеей.