CF1675E Replace With the Previous, Minimize 题解

FFTotoro · 2022-05-12 21:13:11 · 题解

观察题目，我们可以得到大致思路：

使用贪心，从前往后扫一遍，根据题意找到某种字符可以降到的下限，暴力地从前扫到后更新每个字符，最后再扫一遍，把没有完全更新的字符变成 a 即可。

放代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  int t; cin>>t;
  while(t--){
    int n,k; string s; cin>>n>>k>>s; char c=97; // 初始化字符变量 c
    for(int i=0;i<n;i++)
      if(s[i]>c){ // 只有更大才有意义继续更新
        if(s[i]-97>k){
          k-=c-97; int mn=s[i]-k; // 找到最低可以降到多少
          for(char h=s[i];h>mn;h--)
            for(int j=0;j<n;j++)
              if(s[j]==h)s[j]=h-1; // 暴力地扫一遍，如果可以降那么就更新
          break;
        }
        else if(c<s[i])c=s[i]; // 更新最低的值，以便最后的更改
      }
    for(int i=0;i<n;i++)
      if(s[i]<=c)s[i]='a'; // 更新成 'a'
    cout<<s<<endl;
  }
  return 0;
}