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

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

Задана строка 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 не существует.



Комментарии

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


© 2020 HSECODES [email protected] Карта сайта