Решение задачи "Ступени" с Codeforces

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


Наташа собирается полететь на Марс. Ей необходимо построить ракету, которая собирается из нескольких ступеней в определённом порядке. Каждая из ступеней описывается одной строчной буквой латинского алфавита. Тем самым ракета описывается строкой — конкатенацией букв, соответствующих ступеням.

Всего на складе есть n ступеней. Ракета должна содержать ровно k из них. Ступени в ракете должны быть упорядочены по весу. После ступени с некоторой буквой можно ставить только ступень с буквой, идущей хотя бы на две позиции позже в алфавите (то есть через одну букву или более). Например, после буквы 'c' нельзя ставить буквы 'a', 'b', 'c' и 'd', зато можно ставить 'e', 'f', ..., 'z'.

Чтобы ракета летела максимально далеко, нужно, чтобы её вес был минимален. Вес ракеты равен сумме весов её ступеней. Ступень весит столько тонн, каков номер её буквы в алфавите. Иными словами, ступень 'a' весит одну тонну, 'b' весит две тонны, а 'z' — 26 тонн.

Постройте ракету минимального веса или скажите, что ни одной ракеты построить нельзя. Каждую из ступеней на складе можно использовать не более одного раза.

Код

#include <bits/stdc++.h>
using namespace std;

const int N = 100100;

int n, k, i, prv = -100, ans;
string s;

int main() {
	cin >> n >> k >> s;
	sort(s.begin(), s.end());

	for (i = 0; k > 0 && i < s.size(); ++i) {
		if (s[i] - 'a' > prv + 1) {
			prv = s[i] - 'a';
			ans += s[i] - 'a' + 1;
			k--;
		}
	}

	cout << (k > 0 ? -1 : ans) << endl;
	return 0;
}

         

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


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

Комментарии

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