567 . Peach 還是好閒

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

abcabcabc

User's AC Ratio

50.0% (1/2)

Submission's AC Ratio

50.0% (1/2)

Tags

apcsc apcsc-string

Description

暑假的桃子真的太閒了，就連瘋狂的打出 qwq （請參考 p816 ）也止不住寂寞。

這天桃子又隨手打出了一個只由小寫英文字母組成的字串 $s$，他突發奇想，想試著利用一些操作來讓這個字串的字典序變的最小：

  • 從 a 到 z 選一個字母，並且將 $s$ 裡面所有的該字母通通置換為字典序上的前一個字母，舉例而言，把所有的 c 都替換為b；要特別注意的是，選擇 a 時會將所有的字母 a 通通替換為字母 z。

但因為桃子有點睏了，剩下的時間只夠他進行最多 $k$ 次操作，你決定告訴桃子在進行不超過 $k$ 次的操作之後，所能獲得的最小字典序的字串為何，好讓桃子可以安心睡覺。

Input Format

輸入的第一行有一個整數 $t\ (1\le t\le 10^ 4)$，代表測資的數量。

每一筆測資的第一行有兩個整數 $n, k\ (1\le n\le 2\times 10^ 5, 1\le k\le 10^ 9)$，分別代表桃子打出來的字串長度以及最多可進行的操作數量，兩者之間以空格分隔。

第二行則是一個長度為 $n$ 的字串 $s$，代表桃子打出來的字串，$s$ 只包含小寫字母。

保證所有測資的 $n$ 的總和不超過 $2\times 10^ 5$

Output Format

對於每筆測資請輸出一行，包含一個字串，代表 $s$ 在經過不超過 $k$ 次操作之後，所能獲得的最小字典序的字串。

Sample Input 1

4
3 2
cba
4 5
fgde
7 5
gndcafb
4 19
ekyv

Sample Output 1

aaa
agaa
bnbbabb
aapp

Hints

Problem Source

CodeForces 1675E

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 0~15 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 2
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
11 1000 524288 65536 2
12 1000 524288 65536 2
13 1000 524288 65536 2
14 1000 524288 65536 2
15 1000 524288 65536 2
Submit
Back to Top