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

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

Задана строка s, состоящая из n строчных букв латинского алфавита.

Вам необходимо удалить из строки не более одного (то есть ноль или один) символа таким образом, что строка, которую вы получите, будет являться лексикографически минимальной среди всех строк, которые можно получить при помощи этой операции.

Строка s=s1s2…sn лексикографически меньше строки t=t1t2…tm, если n
Например, «aaa» меньше, чем «aaaa», «abb» меньше, чем «abc», «pqr» меньше, чем «z».

Код 

#include <bits/stdc++.h>

using namespace std;
int main()
{
	int n;
	string s;
	cin >> n >> s;
	int a = n - 1;
	for(int i = 0;i < n - 1;i++){
		 if(s[i] > s[i + 1]){
		  	a = i;
		  	break;
		  }
	}
	s.erase(a,1);
	cout << s;
	return 0;
	}

         

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


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

По определению лексикографического сравнения мы можем увидеть, что если мы можем удалить один символ, мы всегда должны это сделать. Кроме того, мы должны удалить символ с самой левой позиции i такой, что is[i+1] или же с позиции n, если такого i не существует.


Комментарии

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



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

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

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