Матч 217, Игра (PlayGame)

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

В компьютерной игре Ваша армия сражается с вражеской. Армии выстраиваются в ряд друг против друга так, что перед каждым Вашим воином стоит воин оппонента. Воины имеют силу, которая выражается натуральным числом. В бою сражаются только воины, которые находятся друг против друга (число воинов обоих армий одинаково). Ваш воин выигрывает, если его сила строго больше силы воина соперника. Известно начальное расположение воинов соперника. Требуется так расставить Ваших воинов, чтобы после окончания боя суммарное значение сил оставшихся в живых с Вашей стороны было максимальным.

Класс: PlayGame

Метод: int saveCreatures(vector<int> you, vector<int> computer)

Ограничения: 1 £ you[i], computer[i] £ 1000, размер массивов you и computer не более 50.

Вход. Состав Вашей армии you и армии оппонента computer.

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

Пример входа

you	computer
{5, 15, 100, 1, 5}	{5, 15, 100, 1, 5}
{1, 3, 5, 7, 9, 11, 13, 15, 17, 19}	{2, 4, 6, 8, 10, 12, 14, 16, 18, 20}
{651, 321, 106, 503, 227, 290, 915, 549, 660, 115, 491, 378, 495, 789, 507, 381, 685, 530, 603, 394, 7, 704, 101, 620, 859, 490, 744, 495, 379, 781, 550, 356, 950, 628, 177, 373, 132, 740, 946, 609, 29, 329, 57, 636, 132, 843, 860, 594, 718, 849}	{16, 127, 704, 614, 218, 67, 169, 621, 340, 319, 366, 658, 798, 803, 524, 608, 794, 896, 145, 627, 401, 253, 137, 851, 67, 426, 571, 302, 546, 225, 311, 111, 804, 135, 284, 784, 890, 786, 740, 612, 360, 852, 228, 859, 229, 249, 540, 979, 55, 82}

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

120

99

25084

РЕШЕНИЕ

жадный алгоритм

Отсортируем воинов обоих армий по возрастанию их силы. Следует выставить Вашего самого сильного воина против самого сильного воина оппонента, которого он может одолеть. Потом перейти к следующему по силе Вашему воину и найти ему таким же образом оппонента и так далее.

ПРИМЕР

Рассмотрим первый пример. Отсортируем армии по возрастанию сил воинов:

you = {1, 5, 5, 15, 100}

computer = {1, 5, 5, 15, 100}

Вашего самого сильного воина (с силой 100) следует выставить против компьютерного воина с силой 15 – самого сильного воина оппонента, которого он может победить. Следующего воина с силой 15 следует выставить против 5. Вашего воина с силой 5 выставляем против оппонента с силой 1. Все остальные Ваши воины будут разбиты. Таким образом, после боя сумма сил выживших Ваших воинов будет максимально возможной и равной 100 + 15 + 5 = 120.

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <algorithm>

using namespace std;

class PlayGame

{

public:

int saveCreatures(vector<int> you, vector<int> computer)

{

int you_ptr, comp_ptr, res = 0;

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

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

you_ptr = comp_ptr = you.size() - 1;

while(comp_ptr >= 0)

{

if (you[you_ptr] > computer[comp_ptr])

{

res += you[you_ptr];

you_ptr--;

}

comp_ptr--;

}

return res;

}

};