链接
题目
小写字符 的 数值 是它在字母表中的位置（从 1 开始），因此 a 的数值为 1 ，b 的数值为 2 ，c 的数值为 3 ，以此类推。
字符串由若干小写字符组成，字符串的数值 为各字符的数值之和。例如，字符串 "abe" 的数值等于 1 + 2 + 5 = 8 。
给你两个整数 n 和 k 。返回 长度 等于 n 且 数值 等于 k 的 字典序最小 的字符串。
注意，如果字符串 x 在字典排序中位于 y 之前，就认为 x 字典序比 y 小，有以下两种情况：
x 是 y 的一个前缀；
如果 i 是 x[i] != y[i] 的第一个位置，且 x[i] 在字母表中的位置比 y[i] 靠前。
示例
示例 1：
输入：n = 3, k = 27
输出："aay"
解释：字符串的数值为 1 + 1 + 25 = 27，它是数值满足要求且长度等于 3 字典序最小的字符串。示例 2：
输入：n = 5, k = 73
输出："aaszz"
说明
1 <= n <= 10e5n <= k <= 26 * n
思路一 （贪心）
我们可以对题目进行分析，在规定字母个数固定且和相同的情况下，要凑出字典序最小的字符串（也就是大的字母尽量往后放，前面尽量放字母，且越前面字母越小越好），那么我们出发点就是在最前面尽量多的放a，而不行再加别的数，但由于字母个数有限，又要使得相加达到k，那么就只能尽量在最后面放z，从而使得前面的a越多，如示例2中，后面尽量多的放z，前面尽量多的放a，但由于位数有限，后面不能无限的放z，否则可能题目要求的n=5，当3个z的时候就已经超出了要求的和，因此，我们要尽量多的放z，直到目前剩余的和 k-26<还能继续放的n，然后再最前面尽量多的放a，剩下中间一个数放除了a和z剩余的那个。
C++ Code
class Solution {
public:
string getSmallestString(int n, int k) {
string s;
//整个字符串组成形式 aaaXZZZ Z尽量让a越多越好，最后面Z就要越多
while(n>0)
{
if(k-26>=n) //最后面能放多少个z放多少个
{
s+='z';
k-=26;
n-=1;
}
else //Z放完了考虑中间的字母
{
int middle=k-n+1; //中间只放一个字母即可
string A;
A.append(n-1, 'a'); //最前面尽量多的放a
char M='a'+middle-1;
return A+M+s;
}
}
return s;
}
};思路二（鸡兔同笼问题）
根据上一个思路的分析，我们可以得出以下分析：
字符串的形式必然是 aaaXzzz的形式，最前面包括任意个a，中间一个任意字符，最后面任意个z，假设有x1个a，x2个z，且中间字符的值为x3，则可以列出以下方程：
- x1+x2+1=n；——————> x2 = n-x1-1;
- x1+26*x2+x3=k；
得出 x1+26（n-x1-1）+x3 =k；
也就是 x1+26n-26x1-26+x3=k；——————> -25*x1+26*n-26+x3=k;
由于a的个数必然小于等于n，因此，x1≤n，而x3的值也只有26种可能，因此我们可以暴力求解：
C++ Code
class Solution {
public:
string getSmallestString(int n, int k) {
string S;
for(int x1=0;x1<=n;x1++)
{
for(int x3=1;x3<=26;x3++)
{
if(-25*x1+26*n-26+x3==k)
{
S.append(x1, 'a');
char X3='a'+x3-1;
S+=X3;
S.append(n-x1-1, 'z');
return S;
}
}
}
return S;
}
};