传送门

题目描述

给你一个长度为 n n n的字符串，你可以最多修改其中 k k k个字符，要求最后字符串中 a a aa aa最多，问你处理过后的字符串

分析

贪心思路比较明显，记录两个相邻的 a a a之间的距离，然后从小到大填 a a a就可以了，最后有剩下的 k k k的话，在 a a a的左边和右边拓展即可
最后防止这个区间内没有 a a a，从前往后改即可

代码

#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define dl(x) printf("%lld\n",x);
#define di(x) printf("%d\n",x);
#define _CRT_SECURE_NO_WARNINGS
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int INF = 0x3f3f3f3f;
const int N = 5e5 + 10;
const ll mod = 1000000007;
const double eps = 1e-9;
const double PI = acos(-1);
template<typename T>inline void read(T &a) {
    char c = getchar(); T x = 0, f = 1; while (!isdigit(c)) {if (c == '-')f = -1; c = getchar();}
    while (isdigit(c)) {x = (x << 1) + (x << 3) + c - '0'; c = getchar();} a = f * x;
}
int gcd(int a, int b) {return (b > 0) ? gcd(b, a % b) : a;}
struct Node{
    int l,r;
    bool operator < (Node const &A) const{
        return r - l < A.r - A.l;
    }
};
int n,k;
char str[N];
vector<Node> v;

int main() {
    read(n),read(k);
    scanf("%s",str + 1);
    int last = 1;
    while(str[last] != 'a' && last <= n) last++;
    for(int i = last + 1;i <= n;i++){
        if(str[i] == 'a' && last == i - 1) last = i;
        else if(str[i] == 'a'){
            v.pb({last,i});
            last = i;
        }
    }
    sort(all(v));
    for(int i = 0;i < v.size() && k;i++){
        int l = v[i].l + 1,r = v[i].r - 1,len = r - l + 1;
        if(len <= k){
            for(int j = l;j <= r;j++) str[j] = 'a';
            k -= len;
        }
        else{
            for(int j = l;j < l + k;j++) str[j] = 'a';
            k = 0;
        }
    }
    for(int i = 1;i <= n && k;i++){
        if(str[i - 1] == 'a' && str[i] != 'a') str[i] = 'a',k--;
    }
    for(int i = n;i && k;i--){
        if(str[i + 1] == 'a' && str[i] != 'a') str[i] = 'a',k--;
    }
    for(int i = 1;i <= n && k;i++){
        if(str[i] != 'a') str[i] = 'a',k--;
    }
    int res = 0;
    for(int i = 1;i < n;i++) if(str[i] == 'a' && str[i + 1] == 'a') res++;
    di(res); 
    printf("%s\n",str + 1);
}

/**
*　　┏┓　　　┏┓+ +
*　┏┛┻━━━┛┻┓ + +
*　┃　　　　　　　┃
*　┃　　　━　　　┃ ++ + + +
*  ████━████+
*  ◥██◤　◥██◤ +
*　┃　　　┻　　　┃
*　┃　　　　　　　┃ + +
*　┗━┓　　　┏━┛
*　　　┃　　　┃ + + + +Code is far away from 　
*　　　┃　　　┃ + bug with the animal protecting
*　　　┃　 　 ┗━━━┓ 神兽保佑,代码无bug　
*　　　┃ 　　　　　　 ┣┓
*　　  ┃ 　　　　　 　┏┛
*　    ┗┓┓┏━┳┓┏┛ + + + +
*　　　　┃┫┫　┃┫┫
*　　　　┗┻┛　┗┻┛+ + + +
*/