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

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


У вас есть строка s длины n состоящая только из символов > и <. Вы можете выполнять операции с этой строкой, для каждой операции вы выбираете какой-то символ этой строки, еще не удаленный из нее. Если вы выбрали символ >, следующий символ удаляется (если выбранный вами символ стоит правее всех остальных — ничего не происходит). Если вы выбрали символ <, то предыдущий символ удаляется (если выбранный вами символ стоит левее всех остальных — ничего не происходит).

Например, если мы выберем символ > в строке > > < >, то строка превратится в > > >. А если мы выберем символ < в строке > <, то строка превратится в <.

Строка называется хорошей, если существует последовательность операций, после выполнения которой в строке останется ровно один символ. Например строки >, > > хорошие.

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

Код

#include <bits/stdc++.h>

using namespace std;

int t, n;
string s;

int main(){
	cin >> t;
	for(int tc = 0; tc < t; ++tc){
		cin >> n >> s;
		int res = n - 1;
		for(int i = 0; i < n; ++i)
			if(s[i] == '>' || s[n - 1 - i] == '<')
				res = min(res, i);
		
		cout << res << endl;
	}

	return 0;
}

         

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


Строка хорошая, если её первый символ равен > или последний символ равен <. Строки вида < … > не являются хорошими, так как их первый и последний символы никогда не поменяются, и в итоге они придут к виду < >.

Таким образом, ответ равен минимуму среди количества символов слева от первого символа > и количества символов справа от последнего символа <.


Комментарии

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