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

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

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

Всего на складе есть 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 Автор: Администратор



Комментарии

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



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

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

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