Матч 332, Создание пар (CreatePairs)

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

Имеется список целых чисел. Разрешается группировать числа в пары. Некоторые числа можно оставить без пар. Находится сумма произведений чисел, стоящих в парах, и чисел, стоящих вне пар. Разбиение на пары следует провести таким образом, чтобы полученная сумма была наибольшей.

Класс: CreatePairs

Метод: int maximalSum(vector<int> data)

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

Вход. Целочисленный массив data.

Выход. Максимально возможное значение указанной суммы.

Пример входа

data

{0, 1, 2, 4, 3, 5}

{-1}

{1, 1}

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

27

-1

2

РЕШЕНИЕ

математика

Объединять в пару положительное и отрицательное число нет смысла, поэтому следует отдельно объединять в пары положительные и отрицательные числа. Нули следует обрабатывать отдельно как исключительный случай. Единицы тоже, так как объединение единицы с любым числом не изменяет само число. Имеем следующие четыре группы чисел:

· А: нули;

· Б: единицы;

· В: целые числа, большие 1;

· Г: целые числа, меньшие 0;

Тогда обработку чисел из групп следует производить следующим образом:

Числа из группы Б следует оставить без пары;

Отсортируем числа группы В по убыванию. Объединим в пары соседние числа каждой группы, начиная с наибольшего. В случае нечетного количества чисел в этой группе бкз пары останется наименьший элемент;

Отсортируем числа группы Г по убыванию. Совершим объединение чисел в пары таким же образом, как и в пункте В (произведение двух отрицательных чисел дает положительное значение). Если группа А не пустая, сгруппируем наименьший оставшийся элемент без пары (если таковой имеется) с нулем;

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <algorithm>

using namespace std;

class CreatePairs

{

public:

int maximalSum(vector<int> data)

{

int ones, zeroes, i, res;

vector<int> pos, neg;

for(ones = zeroes = i = 0; i < data.size(); i++)

if (data[i] == 0) zeroes++; else

if (data[i] == 1) ones++; else

if (data[i] > 1) pos.push_back(data[i]); else

neg.push_back(data[i]);

if (pos.size() % 2) pos.push_back(1);

if (neg.size() % 2)

if (zeroes > 0) neg.push_back(0);

else neg.push_back(1);

sort(pos.begin(),pos.end());

sort(neg.begin(),neg.end());

res = ones;

for(i = 0; i < pos.size() / 2; i++) res += pos[2 * i] * pos[2 * i + 1];

for(i = 0; i < neg.size() / 2; i++) res += neg[2 * i] * neg[2 * i + 1];

return res;

}

};