Матч 307, Обмен ботинками (BootsExchange)

Дивизион 2, Уровень 1

Фабрика, производящая обувь, передала магазину n левых и n правых ботинков. Каждый ботинок имеет определенный размер. Левый и правый ботинок образуют пару, если они имеют одинаковый размер. Каждый ботинок может принадлежать только одной паре. Магазин хочет составить n пар, поменяв при этом у фабрики наименьшее количество ботинок.

Массивы left и right содержат размеры соответственно левых и правых ботинков, поступивших из фабрики в магазин. Размер каждого массива равен n.

Класс: BootsExchange

Метод: int leastAmount(vector<int> left, vector<int> right)

Ограничения: left и right содержат одинаковое количество элементов, от 1 до 50 элементов, 1 £ left[i], right[i] £ 1000.

Вход. Массивы left и right, содержащие размеры соответственно левых и правых ботинков.

Выход. Наименьшее количество ботинков, которое следует поменять для образования n пар.

Пример входа

left	right
{1, 3, 1}	{2, 1, 3}
{1, 3}	{2, 2}
{1, 2, 3, 4, 5, 6, 7}	{2, 4, 6, 1, 3, 7, 5}

Пример выхода

1

2

0

РЕШЕНИЕ

обработка массива

Заведем массив Count размера 1001, каждую ячейку которого Count[i] будем увеличивать на 1, если пришел левый ботинок размера i, и уменьшать на 1, если пришел правый ботинок размера i. Если по размеру i излишков нет (то есть количество левых ботинков размера i равно количеству правых того же размера), то по окончанию обработки Count[i] будет равняться 0. Иначе модуль значения Count[i] равен числу ботинков, которым не нашлось пар. Сумма

S =

всегда является четным числом и равна числу ботинок, которым нет пары. Половину из них всегда можно поменять так, чтобы получить набор из пар ботинок.

ПРОГРАММА

#include <cstdio>

#include <vector>

using namespace std;

int i,res,Count[1001];

class BootsExchange

{

public:

int leastAmount(vector<int> left, vector<int> right)

{

for(i = 0; i < left.size(); i++)

Count[left[i]]++, Count[right[i]]--;

for(i = res = 0; i < 1001; i++)

res += abs(Count[i]);

return res / 2;

}

};