本文共 1244 字，大约阅读时间需要 4 分钟。

转自官方题解

我们最好的答案是和原串$s$相等

如果达不到,就看一下前$n-1$个字母是否能相等,如果还达不到就看一下前$n-2$个字母能不能相等…

于是我们从后往前枚举第$k$个位置,判断$[1,k-1]$和原串相等,在第$k$个位置大于原串是否可行

基于这个贪心准则,我们计算一个$cnt[i]$表示$[1,k-1]$中字母$i$的出现次数

然后计算一个$sum$表示如果$[1,k-1]$和原串相等,最少需要补齐多少个字母变成$k$的倍数

$sum=\sum _{i=0}^{25}(k-cnt[i]\%k)\%k$

但是第$k$位比原串大,但是具体放哪个字母呢??

我们可以把这个字母贪心的从$s[k]+1$枚举到${}^{\prime }{z}^{\prime }$,看最好能放哪个字母

在第$k$位放字母$w$,显然需要更新$sum$,此时如果$i+sum<=n$说明是可行的

因为第$k$位比较大,已经保证了字典序比较大,后续只需要满足字母是$k$的倍数即可

没有填满的部分全部填${}^{\prime }{a}^{\prime }$即可

因为n是k的倍数,前面填充的部分用sum补齐了,所以也是k的倍数。

那么剩下的部分也一定是k的倍数,所以贪心放a没有问题

#include 
   
    using namespace std;const int maxn = 3e5+10;int cnt[27],n,k;string s;int get(int x){
    return (k-x%k)%k; }int main(){
   	int t; cin >> t;	while( t-- )	{
   		cin >> n >> k >> s;		for(int i=0;i
    
     =0;i--)			{
   				sum = sum-get( cnt[s[i]-'a'] )+get( --cnt[s[i]-'a'] );				for(int j=s[i]-'a'+1;j<=25;j++)//枚举放哪个字母				{
   					int las = sum;					sum = sum-get( cnt[j] )+get( ++cnt[j] );					if( (i+1)+sum<=n )					{
   						for(int pos=0;pos
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/114481976 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！