1493 C. K-beautiful Strings(從后往前貪心[官方題解])

LINK

另一種解法,自己的解法

轉自官方題解

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

如果達不到,就看一下前 n ? 1 n-1 n?1個字母是否能相等,如果還達不到就看一下前 n ? 2 n-2 n?2個字母能不能相等…

于是我們從后往前列舉第 k k k個位置,判斷 [ 1 , k ? 1 ] [1,k-1] [1,k?1]和原串相等,在第 k k k個位置大于原串是否可行

基于這個貪心準則,我們計算一個 c n t [ i ] cnt[i] cnt[i]表示 [ 1 , k ? 1 ] [1,k-1] [1,k?1]中字母 i i i的出現次數

然后計算一個 s u m sum sum表示如果 [ 1 , k ? 1 ] [1,k-1] [1,k?1]和原串相等,最少需要補齊多少個字母變成 k k k的倍數

s u m = ∑ i = 0 25 ( k ? c n t [ i ] % k ) % k sum=\sum\limits_{i=0}^{25}(k-cnt[i]\%k)\%k sum=i=0∑25?(k?cnt[i]%k)%k

但是第 k k k位比原串大,但是具體放哪個字母呢??

我們可以把這個字母貪心的從 s [ k ] + 1 s[k]+1 s[k]+1列舉到 ′ z ′ 'z' ′z′,看最好能放哪個字母

在第 k k k位放字母 w w w,顯然需要更新 s u m sum sum,此時如果 i + s u m < = n i+sum<=n i+sum<=n說明是可行的

因為第 k k k位比較大,已經保證了字典序比較大,后續只需要滿足字母是 k k k的倍數即可

沒有填滿的部分全部填 ′ a ′ 'a' ′a′即可

#include <bits/stdc++.h>
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<n;i++)	cnt[s[i]-'a']++;
		int sum = 0, flag = 1;
		for(int i=0;i<=25;i++)	sum += get( cnt[i] );
		if( sum==0 )	cout << s << endl;
		else if( n%k!=0 )	cout << -1 << endl;	
		else
		{
			for(int i=n-1;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<i;pos++)	cout << s[pos];
						cout << char( j+'a' );
						for(int pos=1;pos<=n-sum-(i+1);pos++)	cout << 'a';
						for(int w=0;w<=25;w++)
						{
							int f = get( cnt[w] );
							while( f )	f--,cout << char( w+'a' );
						}
						cout << endl; flag = 0;
						break;
					}
					cnt[j]--; sum = las;	
				}
				if( flag==0 )	break; 
			}
		}
		memset( cnt,0,sizeof cnt );
	}
}