[普及/提高-]A104750.题解

题意请自行理解

思路

考虑贪心，发现高位的优先级永远比低位高，即 yzzz.... 一定比 zaaa... 优，即使使高位修改远比低位修改所需花费高得多。故贪心策略是尽可能修改最高位，修改完后需特判比所有字符串都小的情况。

AC code

#include<bits/stdc++.h>
using namespace std;
const int N = 200005;
#define int long long
int n , m , k , b , p[N];
string x , a[N];
signed main(){
    cin >> n >> m >> k >> b;
    cin >> x;
    for(int i = 1;i <= m;i ++){
        cin >> a[i];
    } 
    for(int i = 0;i < n;i ++){
        cin >> p[i];
    }
    for(int i = 0;i < n;i ++){
        if(x[i] == 'a'){
            continue;
        }else if(k == 0){
            break;
        }
        int can = min(b / p[i] , (int)(x[i] - 'a'));
        if(can == 0){
            continue;
        }
        x[i] -= can;
        k --;
        b -= p[i] * can;
    }
    sort(a + 1 , a + 1 + m);
    for(int i = m;i >= 1;i --){
        if(a[i] <= x){
            cout << i + 1 << endl << x;
            return 0;
        }
    }
    cout << 1 << endl << x;
    return 0;
}