C. K-beautiful Strings

https://codeforces.ml/contest/1493/problem/C

思路

题目大意为给出一个字符串，通过将其中任何字母进行替换(或不进行任何操作)得到一个好的序列，其中每个字母的出现次数为k的倍数；

如果不存在这样的序列输出-1；
如果存在则在所有可能的序列中找出在大于等于原序列的基础上最小的序列(此处的>、<和=是根据字典序来判断的)
一开始不会做，看了官方题解恍然大悟

• 对于不存在的情况，即：n % k != 0,直接输出-1;
• 首先判断给出给出的序列是否满足条件，如果满足直接输出即可;
• 从后向前贪心(因为保证序列尽可能小，就要使更改的部分尽可能在后面)：
  • 统计每个字母得到条件所需的个数(sum)
  • 从后向前遍历，遍历至位置i表示从i到n-1这个位置需要替换，此时在满足条件的情况下只需保证位置i的字母尽可能的小，即从s[i]-'z'遍历，当取得j时满足i + sum < n，则此时就是答案。s[i]=j，剩余位置中取出sum个位置用于填充位置i以前的字母使其满足条件，剩余位置全部填充'a'即可(因为保证尽可能小)，注意(i+1)-(n-1)这部分字符串需要进行排序保证尽可能小，因为位置i已经满足大于原序列的条件了，最后输出答案即可。

Code

#include<bits/stdc++.h>
#define IO  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define req(i,a,b) for(int i=a;i>=b;i--)
using namespace std; 
 
const int inf=0x3f3f3f3f;
typedef long long ll; 
const int N = 1e5+7;
const ll mod = 1e9+7;  

int main(){ 
    IO;
    int t=1;
    cin>>t;
    while(t--){  
        int n,k;
        string s;
        cin>>n>>k>>s;
        int a[30]={0};
        int sum=0;
        if(n%k){
            cout<<-1<<endl;
            continue;
        }
        for (int i = 0; i < n; ++i)
        {
            a[s[i]-'a']++;
        }
        for (int i = 0; i < 26; ++i)
        {
            sum+=(k-a[i]%k)%k;
        }
        if(sum==0){
            cout<<s<<endl;
            continue;
        }int flag=0;
        for (int i = n-1; i >= 0; --i)
        {
            sum-=(k-a[s[i]-'a']%k)%k;
            a[s[i]-'a']--;
            sum+=(k-a[s[i]-'a']%k)%k;
            for (int j = s[i]-'a'+1; j < 26; ++j)
            {
                int p=sum;
                sum-=(k-a[j]%k)%k;
                a[j]++;
                sum+=(k-a[j]%k)%k;
                if(i+sum<n){
                    flag=1;
                    for (int p = 0; p < i; ++p)
                    {
                        cout<<s[p];
                    }cout<<char(j+'a');
                    string x;
                    for (int p = 0; p < 26; ++p)
                    {
                        int cnt=(k-a[p]%k)%k;
                        while(cnt--)x+=char(p+'a');
                    }
                    for (int p = i+sum+1; p < n; ++p)
                    {
                        x+='a';
                    }sort(x.begin(),x.end());
                    cout<<x<<endl;
                    break;
                }
                a[j]--;
                sum=p;
            }
            if(flag)break;
        }
    }
    return 0;
}