Решение задачи "Феникс и распределение" с Codeforces

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


У Феникса есть строка s, состоящая из строчных букв латинского алфавита. Он хочет распределить все буквы своей строки по k непустым строкам a1,a2,…,ak так, что каждая буква из s попадет ровно в одну из строк ai. Строки ai не обязаны быть подстроками s. Феникс может распределить буквы s и переупорядочить их внутри каждой строки ai так как захочет.

Например, если s= baba и k=2, Феникс может распределить буквы своей строки множеством способов, в том числе:

ba и ba
a и abb
ab и ab
bb и aa
Однако получить такие варианты он не может:

baa и ba
b и ba
baba и пустая строка (ai должны быть непустыми)
Феникс хочет разделить свою строку s на k строк a1,a2,…,ak так, чтобы минимизировать лексикографически максимальную строку среди них, т. е. минимизировать max(a1,a2,…,ak). Помогите ему найти оптимальное распределение и выведите минимально возможное значение max(a1,a2,…,ak).

Строка x лексикографически меньше, чем строка y, если либо x является префиксом y (и x≠y), либо существует такой индекс i (1≤i≤min(|x|,|y|)), что xi < yi и для всех j (1≤j

Код

#include <bits/stdc++.h>
using namespace std;
int t, n, k; string s;
int main(){
	cin >> t;
	while(t--){
		cin >> n >> k >> s;
		sort(s.begin(), s.end());
		if (s[0] != s[k - 1]) cout << s[k - 1] << '\n';
		else {
			cout << s[k - 1];
			if (s[k] != s[n - 1])
				for (int i = k; i < n; i++) cout << s[i];
			else 
				for (int i = 0; i < (n - k - 1) / k + 1; i++) cout << s[k];
			cout << '\n';
		}
	}
	return 0;
}

         

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


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

Комментарии

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