C. K-beautiful Strings Codeforces Round #705 (Div. 2)题解

题目链接：C. K-beautiful Strings
题意：略
思路：本来这题我的思路是错误的，当时也考虑贪心的做法，但想法还是不完备，参考了大神的做法之后写出来了一份代码，方法是对于从n-1到0的每一位进行考虑，因为题目说的是目标串要大于等于当前串，于是我们肯定只从后往前改最少位才能获得最优解，如果还不理解，你可以将他看成是一个26进制数，肯定是最好不动高位数才能满足大于等于且“最小”这个操作，然后具体思路是，我们可以维护一个数，该数的意义是当前至少需要多少个字母才能把当前位置之前的字母凑齐，然后我们不断维护该数，当该数小于等于该位置到尾部位置时就可以退出进行赋值。复杂度\(\Theta(26*n)\)
\(Coding:\)

#include<set>
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<map>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(auto i=a;i<=b;++i)
#define bep(i,a,b) for(auto i=a;i>=b;--i)
#define lowbit(x) (x&(-x))
#define ch() getchar()
#define pc(x) putchar(x)
using namespace std;

template<typename T>void read(T&x){
static char c;static int f;
for(c=ch(),f=1;c<‘0‘||c>‘9‘;c=ch())if(c==‘-‘)f=-f;
for(x=0;c>=‘0‘&&c<=‘9‘;c=ch())x=x*10+(c&15);x*=f;
}
template<typename T>void write(T x){
static char q[65];int cnt=0;
if(x<0)pc(‘-‘),x=-x;
q[++cnt]=x%10,x/=10;
while(x)
    q[++cnt]=x%10,x/=10;
while(cnt)pc(q[cnt--]+‘0‘);
}
const int N = 2e5+10;
int a[N];
char str[N],c[N];
int cnt[33],cnt2[33];
bool st[N],vis[33];
void solve(){
    int n,k,_;
    read(_);
    while(_--){
        memset(cnt,0,sizeof cnt);
        read(n);read(k);
        scanf("%s",str);
        if(n%k){
            puts("-1");continue;
        }
        rep(i,0,n-1){
            cnt[str[i] - ‘a‘]++;
        }
        int sum = 0;
        rep(i,0,25){
            sum += (k-cnt[i]%k)%k;
        }
        if(sum == 0){
            puts(str);
            goto stk;
        }
        bep(i,n-1,0){
            int dis = n - i;
            sum -= (k - cnt[str[i] - ‘a‘]%k)%k;
            cnt[str[i] - ‘a‘]--;
            sum += (k - cnt[str[i] - ‘a‘]%k)%k;
            //printf("%d %d\n",i,sum);
            //if(sum > dis)continue;
            int now = i,id = -1;
            rep(j,str[i]-‘a‘+1,25){
                int x = sum;
                sum -= (k - cnt[j]%k)%k;
                cnt[j]++;
                sum += (k - cnt[j]%k)%k;

                //printf("%d:%d %d\n",i,j,sum);
                if(sum<=dis-1){
                    //cnt[j]++;
                    id = j;break;
                }
                else sum = x,cnt[j]--;
            }
            if(id!=-1){
                str[i] = id + ‘a‘;
                int h = n-1;//cnt[0] = 888888;
                rep(j,0,25)cnt2[j] = (k - cnt[j]%k)%k;
                cnt2[0] = 888888;
                while(h>=i+1){
                    //bool flag = false;
                    bep(j,25,0)if(cnt2[j]){str[h] = j+‘a‘;cnt2[j]--; break; }h--;
                }
                puts(str);
                goto stk;
            }
        }
        //puts("-2");
        stk:;

    }
}
signed main(){
    solve();
    return 0;
}

C. K-beautiful Strings Codeforces Round #705 (Div. 2)题解

原文：https://www.cnblogs.com/violentbear/p/14633116.html