Решение задачи Хорошая строка с Codeforces

С пояснением   Просмотров: 1849

Давайте назовем (ага, опять) строку хорошей, если ее длина четна, и каждый нечетный символ этой строки отличается от следующего за ним (первый символ отличается от второго, третий — от четвертого, и так далее). Например, строки good, string и xyyx — хорошие, а строки bad, aa и aabc — нет. Обратите внимание, что пустая строка является хорошей строкой.

Вам дана строка s. Удалите из нее минимальное количество символов так, чтобы она стала хорошей.

Код 

#include<bits/stdc++.h>

using namespace std;

string s;
int n;
string res;

int main()
{
	cin >> n >> s;
	for(int i = 0; i < n; i++)
	{
		if(res.size() % 2 == 0 || res.back() != s[i])
			res.push_back(s[i]);
	}
	if(res.size() % 2 == 1) res.pop_back();
	cout << n - int(res.size()) << endl << res << endl;
	return 0;
}

         

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


Пояснение к задаче

Работает следующее жадное решение: пройдем по всем символам строки слева направо, и если последний блок двух последовательных символов в результирующей строке полон, просто добавим текущий символ к результирующей строке, иначе добавим этот символ в том случае, если он не равен первому символу последнего блока. И не забудьте по поводу четности длины (удалим последний символ, если длина нечётна).


Комментарии

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



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

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

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