Решение задачи Удаления с меняющейся четностью с Codeforces

Без пояснения   Просмотров: 1481

У Поликарпа есть массив a, состоящий из n целых чисел.

Он хочет поиграть в игру с этим массивом. Игра состоит из нескольких шагов. Во время первого хода он выбирает любой элемент и удаляет его (после первого хода массив содержит n−1 элемент). Для каждого из следующих ходов он выбирает любой элемент с одним ограничением: его четность должна отличаться от четности элемента, удаленного во время прошлого хода. Другими словами, он меняет четности (четный-нечетный-четный-нечетный-... или нечетный-четный-нечетный-четный-...) удаляемых элементов. Поликарп останавливается, если не может совершить ход.

Формально:

Если сейчас первый ход, он выбирает элемент и удаляет его;
Если это второй или любой следующий ход:
если последний удаленный элемент был нечетным, Поликарп выбирает любой четный элемент и удаляет его;
если последний удаленный элемент был четным, Поликарп выбирает любой нечетный элемент и удаляет его.
Если после какого-то хода Поликарп не может сделать ход, игра заканчивается.
Цель Поликарпа — минимизировать сумму неудаленных элементов массива после конца игры. Если Поликарп может удалить массив целиком, тогда сумма неудаленных элементов равна нулю.

Помогите Поликарпу найти это значение.

Код 

#include<iostream>
#include<algorithm>
using namespace std;
int x,oi,ei,r,o[2200],e[2200];
int main()
{
	int n;
	cin>>n;
	for(int i;i<n;i++)
	{
		cin>>x;
		if(x%2==0) o[oi++]=x;
		else e[ei++]=x;
	}
	sort(o,o+oi);
	sort(e,e+ei);
	if(oi>ei)swap(o,e),swap(oi,ei);
	for(int i=0;i<ei-oi-1;i++)
	{
		r +=e[i];
	}
	cout<<r;
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться



info@mycod.net   Карта сайта   Правообладателям
Заявка на расчет
×

или напишите нам прямо сейчас:

Написать в MAX
Написать в Telegram
Написать в WhatsApp