以前写挂了 今天又拿出来写
手玩一下样例发现 我们从高位贪是肯定的
尽可能让该位置和原串一样
然后我们可以枚举该位改成什么字母 然后计算后面的放是否合法
写的很屎 其实就是复制粘贴了一坨
我们先找到 最远的位置可以修改 再修改为最小的即可
void solve(){
int n,k;cin>>n>>k;
string s;cin>>s;s='='+s;
if(n%k){
cout<<-1<<endl;
return;
}
map<int,int>mp;
int P;
for(int i=1;i<=n;i++){
for(int j=s[i]+1;j<='z';j++){
mp[j]++;
int sy=n-i;
for(auto [pos,w]:mp)sy-=k-w;
if(sy>=0&&sy%k==0){
// cout<<i<<' '<<char(j)<<endl;
P=i;
mp[j]--;
if(mp[j]%k==0)mp.erase(j);
break;
}
mp[j]--;
if(mp[j]%k==0)mp.erase(j);
}
mp[s[i]]++;
if(mp[s[i]]%k==0)mp.erase(s[i]);
}
if(mp.size()==0){
cout<<s.substr(1)<<endl;
return;
}
mp.clear();
for(int i=1;i<=P;i++){
for(int j=s[i]+1;j<='z';j++){
mp[j]++;
int sy=n-i;
for(auto [pos,w]:mp)sy-=k-w;
if(sy>=0&&sy%k==0&&i==P){
vector<int>qt;
string ans=s.substr(0,i);
ans+=j;
for(auto [pos,w]:mp){
int syy=k-w;
while(syy--)qt.push_back(pos);
}
while(sy--)qt.push_back('a');
sort(all(qt));
for(auto now:qt)ans.push_back(now);
cout<<ans.substr(1)<<endl;
return;
}
mp[j]--;
if(mp[j]%k==0)mp.erase(j);
}
mp[s[i]]++;
if(mp[s[i]]%k==0)mp.erase(s[i]);
}
cout<<P<<endl;
}
标签:qt,int,CF1493C,back,&&,ans,push
From: https://www.cnblogs.com/ycllz/p/17901243.html