Mr. Takahashi has a string s consisting of lowercase English letters. He repeats the following operation on s exactly K times.
- Choose an arbitrary letter on s and change that letter to the next alphabet. Note that the next letter of
z
isa
.
For example, if you perform an operation for the second letter on aaz
, aaz
becomes abz
. If you then perform an operation for the third letter on abz
, abz
becomes aba
.
Mr. Takahashi wants to have the lexicographically smallest string after performing exactly K operations on s. Find the such string.
题目链接:https://code-festival-2016-quala.contest.atcoder.jp/tasks/codefestival_2016_qualA_c?lang=en
题目大意: 输入一个字符串a,再输入一个数字k,a→b消耗1, a→c消耗2,z→a消耗1,依次如此,为了使这一个字符串的字典序最小,而且k必须用完。 除了最后一个字符,前面的字符如果能变成’a',并且需要m次,则k = k - m; 如果不能变成‘a' 就是次数不够了则k - m < 0 ,然后循环接下来的字符,一直到倒数第二个字符。特判最后一个字符,因为k必须用完。
坑点:
1. 注意判断最后一个字符变成什么的时候,注意k值,k值可能非常大,所以需要进行处理 k = k % 26;
2. 注意对最后一个字符进行变换时得加减顺序,因为会’z'的asc码 为122,asc码一共为127,如果顺序不当,直接爆出
3,必须特判字符是否为’a',如果为‘a'的话,则不需要消耗m,如果不特判,则k会减少二十六
AC代码:
#include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #include<string> #include<cstdlib> #include<iostream> using namespace std; const int MaxN = 1e5 + 5; char a[MaxN]; int main() { int m; long long k; cin >> a; scanf("%lld", &k); long long len = strlen(a); long long j = len - 1; for(int i = 0; i < len - 1; i++) { if(a[i] == 'a') m = 0; // 不特判a的话 m = ’z' - ‘a' + 1 = 26 使得 k减少26 else m = 'z' - a[i] + 1; k = k - m; if(k >= 0) a[i] = 'a'; else k = k + m; } k = k % 26; // 防止k太大 if( k + a[j] > 'z') a[j] = a[j] - 26 + k; // 超出asc码 else a[j] = k + a[j]; cout << a << endl; }